# A better way to do it?

## Recommended Posts

I was supposed to make a list of the prime numbers up until 100. Here it is:

#include <iostream>
using namespace std;

int main()
{
double Prime;
int counter;

cout << "List of prime numbers: " << "\n";

Prime = 2;
cout << Prime << "\n";

Prime = 3;
cout << Prime << "\n";

Prime = 5;
cout << Prime << "\n";

Prime = 7;
cout << Prime << "\n";

Prime = 11;
cout << Prime << "\n";

Prime = 13;
cout << Prime << "\n";

Prime = 17;
cout << Prime << "\n";

Prime = 19;
cout << Prime << "\n";

Prime = 23;
cout << Prime << "\n";

Prime = 29;
cout << Prime << "\n";

Prime = 31;
cout << Prime << "\n";

Prime = 37;
cout << Prime << "\n";

Prime = 41;
cout << Prime << "\n";

Prime = 43;
cout << Prime << "\n";

Prime = 47;
cout << Prime << "\n";

Prime = 53;
cout << Prime << "\n";

Prime = 59;
cout << Prime << "\n";

Prime = 61;
cout << Prime << "\n";

Prime = 67;
cout << Prime << "\n";

Prime = 71;
cout << Prime << "\n";

Prime = 73;
cout << Prime << "\n";

Prime = 79;
cout << Prime << "\n";

Prime = 83;
cout << Prime << "\n";

Prime = 89;
cout << Prime << "\n";

Prime = 97;
cout << Prime << "\n";

std::cin.ignore();
std::cin.get();
return 0;
}

At the end it shows what I wanted it to show but... I'm pretty sure that there is a better, shorter way to do this, and I would like to know it.

Thanks.

##### Share on other sites
a) If you want to keep the results hard-coded, output everything at once without using the fairly redundant prime variable and the completely unused integer counter.
b) The proper way: create a function that will find prime numbers for you.
Quote:
 I was supposed to make a list of the prime numbers

You mean it's home work?

##### Share on other sites
For reference, we don't give answers to homework problems here. We can give you hints or point you in the right direction though, or if you ask specific questions and show us your own attempts we can help you out with solving it yourself.

You have a variable called counter, that you're not using... have you learned about loops yet? Notice your program has a series of almost identical lines of code: if this happens, chances are you should be doing something in a loop rather than doing it by hand repeatedly.

Do you know how to figure out if a number is prime or not?

Do those hints help? [wink]

##### Share on other sites
You need to use a loop that checks within the loop if the current number is 100. Example:

for (int i=100;i<=100;i++)
{

//check if "i" is a prime number

}

##### Share on other sites
Hehe, no this is not homework. Well, sort of, I'm studying the C++ book, and the book gives me assignments. And technically, I did it. I was just wondering if there was an easier way to do what I did.

Ok, int counter is a mistake, I wanted to do a loop but I didn't know how to do a loop that would count Prime numbers only, so I scratched that and went the hardcore way.

Now, can anyone please explain, not just tell, an easier way to do this?

##### Share on other sites
Have you covered arrays or containers in your book yet?

##### Share on other sites
Hmm.. I'm not sure. Probably not.

##### Share on other sites
Quote:
 Original post by D4rk_AngelI wanted to do a loop but I didn't know how to do a loop that would count Prime numbers only, so I scratched that and went the hardcore way.
If we picked some random number and asked you whether or not it was prime, would you be able to figure it out? What makes a number prime?

##### Share on other sites
Yeah, it's a number that you cannot factorize, right?

##### Share on other sites
The author of the book probably wants you to make a program that determines which numbers between 1 and 100 is a prime, and print it if it is.

To do this, loops and the modulo operator (%) would come in handy, as well as the square root function (sqrt)

Note in particular the section called "Verifying primality"

quote:
"The most basic method to do this, known as trial division, works as follows: given a number n, one divides n by all numbers m less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime."

##### Share on other sites
Quote:
 Original post by D4rk_AngelYeah, it's a number that you cannot factorize, right?
That's the point of the exercise :)
You're supposed to write an algorithm that can determine if a number can be factorised, and then use this algorithm to test the numbers from 1 to 100.

These links should give you an idea of how to write your algorithm:
The C++ Modulus Operator
Primality test

##### Share on other sites
Quote:
 Original post by agislerYou need to use a loop that checks within the loop if the current number is 100. Example:for (int i=100;i<=100;i++){//check if "i" is a prime number}

I realize it's a typo, but just to avoid any confusing for OP: you start counting at one (and you can skip the even numbers obviously). [smile]

##### Share on other sites
Edit Bug fix, pointed out by SiCrane.

for (int test_value = 1; test_value <= 100; test_value++){    if( is_prime(test_value) ){        cout << test_value << endl;    }}

All that remains is to write the function called is_prime().

[Edited by - AngleWyrm on October 10, 2010 10:32:00 AM]

##### Share on other sites
Quote:
 Original post by AngleWyrm *** Source Snippet Removed ***All that remains is to write the function called is_prime().

That algorithm will miss the prime 2.

##### Share on other sites
Thanks for everything, you guys. But I don't think that I'm at that level just yet.

##### Share on other sites
Can you describe a procedure for determining if a number is prime or not?

This is the heart of programming; procedural thinking.

Forget about the language for a minute and try to describe a procedure. If I give you the number 42, can you describe a process that proves it is or is not a prime?

##### Share on other sites
It is not prime because:

42 | 2
21 | 3
7 | 7
1
42 is a composite number.

##### Share on other sites
Quote:
 Original post by JoeCooperIf I give you the number 42, can you describe a process that proves it is or is not a prime?

Start with the square root of 42, and work down towards 2.
Sqrt(42) = 6.48, so begin with 6.
42/6 = 7. Oops, found an exact match, so it's not prime.
If 6 hadn't divided evenly into 42, we'de move on to 5:
42/5 = 8.4, not an integer, keep going
42/4 =10.5, not an integer, keep going
42/3 =14. Oops, found an integer divisor greater than 1, so not a prime
42/2 =21. Found an integer divisor greater than one, so not prime.

But really, only have to stop at the first one that divides evenly, which was 6. Putting it into source code:

#include <iostream>#include <cmath>using namespace std;bool is_prime(int test_value);int main(){    for(int test=1; test<=100; test++){        if( is_prime(test) ){            cout << test << endl;        }    }}bool is_prime(int test_value){    int divisor = (int) sqrt(test_value);    while(divisor >= 2){        if (test_value % divisor == 0){            return false;        }        divisor--;    }    return true;}

[Edited by - AngleWyrm on October 10, 2010 11:49:26 AM]

##### Share on other sites
I'm such a dunce, I wrote a post expanding on all of that and how to check if a number is evenly divisible and completely forgot about the modulus operator. That little % sign in AngleWyrm's example is called the modulus operator and is used to check if a number is evenly divisible by another number. It is a critical step in finding primes. Go look it up to better understand the sample.

I think it might also be worth explaining casting. In Wyrm's example:

int divisor = (int) sqrt(test_value);

sqrt() takes and returns a double, which is like a float but more precise. It lets you store non-whole numbers. sqrt(42) would yield 6.48. But what he wants is 6, not 6.48. So it needs to be converted somehow...

Recall than the int datatype cannot store the number 6.48. If you wrote code like this:

int divisor = sqrt(test_value);

It would take the value 6.48 and shove it into an int slot. (The computer will convert it on the fly.) The value 6 will be stored, which is what's wanted.

But the compiler will give you a warning about an implicit cast. It gives you this warning because in that conversion, data is thrown away, and if you wrote such code on accident, it can break your program. Under some circumstances it could also misunderstand what you want. So...

You must communicate to the compiler that you specifically want to cast it from float to integer.

By putting the target data type in parenthesis before a value, you perform an explicit cast. Here's the code again with the cast highlighted:

int divisor = (int) sqrt(test_value);

Putting that before the value tells the compiler "I want to convert this from its current data type to an int; I understand what this does and have made a conscious decision".

And that will get rid of the warning.

##### Share on other sites
An exercise means: exercise.

You are supposed to do it on your own. Otherwise it's pointless. We really shouldn't help with this kind of stuff.

OP: Do it on your own. If you are not satisfied with the goodness of it, write a better solution.

Okay, forget it...

##### Share on other sites
What szecs says is truth. It was only explained here because the OP appeared to be missing the point entirely about procedural thinking.

For the OP, I have another exercise. No hints. If you understand our explanation of the first one, you can do this one.

It's called "Fizz Buzz".

Count from 1 to 100.

When a number is a multiple of 3, print out "Fizz".

When it is a multiple of 5, print out "Buzz".

When it is a multiple of both 3 and 5, print out "Fizzbuzz".

No hardcoding the results. Don't look it up. Go.

[Edited by - JoeCooper on October 10, 2010 12:39:40 PM]

##### Share on other sites
fizzbuzz is a too common problem. It has trillions of hits with google.

Oh, wait... D'OH!!

##### Share on other sites
Ok, I'll try but if I trouble may I ask a little help? I'm not asking for the solution, just a little hint.

I'm saying this because I only understood a little of the first one. But let me try since this exercise is simple.

##### Share on other sites
Hint: it's like the other one, but asks a moderately simpler question about each number. Don't forget to look up what modulus does; what question it can answer. Carefully read Angle's sample.

##### Share on other sites
Quote:
 Ok, I'll try but if I trouble may I ask a little help?

By the way, these assignments are mathematical, and in my opinion not well suited for someone learning the language. Adding mathematical complexity is typical for programming assignments but can easily discourage people needlessly. Personally I have been programming for almost 20 years and working as a software engineer for some of them and I have never had any use of writing a prime function :D

Anyway, I thought I would give you a hint about the modulus operator as it is not something most people recognize.
I don't know about you but when I think back at elementary school I remember when we learned about multiplying, dividing etc.
Back then we hadn't learned anything about decimal numbers. It was all whole numbers, and when we learned how to divide, our teacher told us that when you can no longer take another divisor out of the dividend without getting a negative number, you are done.
It would typically look like this
23 / 3 = 721 2

That was it. No decimals.
The answer was 7 and the reminder was 2

Now, in C++ programming, if we are working with integer numbers we can get to those values using / and %

23 / 3 = 7
23 % 3 = 2

As you can see the modulus operator (%) gives us the reminder of an integer division. It turns out that getting this reminder is quite useful in many programming tasks.

If you feel this is over your head, don't sweat it. Take your time learning the basics of the language first

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628275
• Total Posts
2981756

• 10
• 11
• 17
• 10
• 9