Sign in to follow this  
D4rk_Angel

A better way to do it?

Recommended Posts

D4rk_Angel    108
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 this post


Link to post
Share on other sites
Wan    1366
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 this post


Link to post
Share on other sites
jbadams    25712
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 this post


Link to post
Share on other sites
agisler    156
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 this post


Link to post
Share on other sites
D4rk_Angel    108
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 this post


Link to post
Share on other sites
jbadams    25712
Quote:
Original post by D4rk_Angel
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.
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 this post


Link to post
Share on other sites
pulpfist    528
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)

There is more info on primes here

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 this post


Link to post
Share on other sites
Hodgman    51334
Quote:
Original post by D4rk_Angel
Yeah, 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 this post


Link to post
Share on other sites
Wan    1366
Quote:
Original post by agisler
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}

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 this post


Link to post
Share on other sites
AngleWyrm    554
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 this post


Link to post
Share on other sites
SiCrane    11839
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 this post


Link to post
Share on other sites
JoeCooper    350
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 this post


Link to post
Share on other sites
AngleWyrm    554
Quote:
Original post by JoeCooper
If 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 this post


Link to post
Share on other sites
JoeCooper    350
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 this post


Link to post
Share on other sites
szecs    2990
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 this post


Link to post
Share on other sites
JoeCooper    350
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 this post


Link to post
Share on other sites
D4rk_Angel    108
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 this post


Link to post
Share on other sites
JoeCooper    350
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 this post


Link to post
Share on other sites
pulpfist    528
Quote:

Ok, I'll try but if I trouble may I ask a little help?

Sure, never hesitate to ask.

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 = 7
21
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this