# Prime Numbers

Show 50 post(s) from this thread on one page
Page 1 of 3 123 Last
• May 12th, 2013, 08:39 PM
rockx
Prime Numbers
I wouldn't be suprised if this question had been posted earlier. But i would like to streamline it a little bit so that i get to know what i m trying to find out......

So if i write a Loop to calculate Prime Numbers in order, is there any way possible for this to happen in a shorter period of time.

the loop that i constructed took about 11hrs on a Win 7 2GB ram machine to calculate about 150,000 primes, could this be done any faster................

Thanks again for any inputs whatsoever.
• May 12th, 2013, 09:06 PM
laserlight
Re: Prime Numbers
Use a better or more appropriate algorithm, e.g., the sieve of Eratosthenes may be applicable.
• May 13th, 2013, 03:45 AM
D_Drmmr
Re: Prime Numbers
Quote:

Originally Posted by rockx
So if i write a Loop to calculate Prime Numbers in order, is there any way possible for this to happen in a shorter period of time.

the loop that i constructed took about 11hrs on a Win 7 2GB ram machine to calculate about 150,000 primes, could this be done any faster................

Did you run a fully optimized build of your program?
• May 13th, 2013, 05:07 AM
2kaud
Re: Prime Numbers
Oh wow! I just tried my prime number generator and it took 672 milliseconds to calculate the first 150,000 prime numbers (39,625 milliseconds to calculate and display them in a console window). I'm using Windows XP 2.37GHz 2Mb memory.

I think you have a problem with your algorithm. As D_Drmmr said in post #3, if you post your code we'll provide guidance.
• May 13th, 2013, 04:37 PM
rockx
Re: Prime Numbers

Code:

```#include <iostream.h> #include <fstream.h> #include <string.h> #include <conio.h> #include <stdlib.h> void main() {         long int i=0,c=1,n,j;         ofstream myfile ("Prime.doc");         if (myfile.is_open()) {         while (c <= 150000)         {                 n=0;                 i +=1;                 for (j=1 ; j<=i ; j++ )                 {                         if ( i%j == 0)                         {                                 n +=1;                                                }                 }                 if (n <=2 && n != 0)                 {                         myfile << c << "=\t"  << i <<"\n\n";                         c +=1;                 }                         }         myfile.close();         }else                 cout << "Unable to open file";   system("PAUSE"); }```
• May 13th, 2013, 05:24 PM
2kaud
Re: Prime Numbers
Try this. I've kept your code structure but just made a couple of changes.:D It completes in a few seconds on my computer.

Code:

```#include <iostream> #include <fstream> #include <string> #include <cstdlib> #include <cmath> using namespace std; int main() { long int        i = 1,                 c = 2,                 n,                 s,                 j; ofstream        myfile ("Prime.doc");         if (myfile.is_open()) {                 myfile << 1 << "=\t"  << 2 <<"\n\n";                 while (c <= 150000) {                         n = 0;                         i += 2;                         s = (long)sqrt((float)i);                         for (j = 3; j <= s; j+=2) {                                 if (i % j == 0) {                                         n += 1;                                                                break;                                 }                         }                         if (n == 0) {                                 myfile << c << "=\t"  << i <<"\n\n";                                 c += 1;                         }                                 }                 myfile.close();         } else                 cout << "Unable to open file";         return 0; }```
• May 13th, 2013, 05:44 PM
rockx
Re: Prime Numbers
Hey thanks buddy, it was complete in less then about 2 seconds on my mchine. so could you please explain as to what was wrong in my code/syntax. and i really appreciate your kind help..... I hope and i wish to learn more ways to improve on my coding from people like you.................... THanks a lot 2Kaud
• May 13th, 2013, 06:14 PM
GCDEF
Re: Prime Numbers
Quote:

Originally Posted by rockx
Hey thanks buddy, it was complete in less then about 2 seconds on my mchine. so could you please explain as to what was wrong in my code/syntax. and i really appreciate your kind help..... I hope and i wish to learn more ways to improve on my coding from people like you.................... THanks a lot 2Kaud

Why don't you watch them both run in the debugger and see what yours is doing compared to his.
• May 14th, 2013, 04:01 AM
2kaud
Re: Prime Numbers
A prime number is a number that is only divisible by itself and 1. The only even prime number is 2. So the first prime numbers (2) can be output immediately. The first number to try for being prime is 3. As every even number is not prime (divisible by 2) then only odd numbers can be prime so the number to test is incremented by 2. If we are only testing odd numbers, then the division test loop can start at 3 and increment by 2 each time (as an odd number divided by an even number always has a remainder). As soon as the remainder is 0 then a non-prime number has been found and the division test loop can be exited. The upper bound for the division test loop is the sqrt of the number to be tested because if a factor is not found in that range that it won't be found in the full range as a number squared always has itself as a factor.

As laserlight stated in post #2, there are other algorithms that can used to determine prime numbers (eg the sieve of Eratosthenes). Another way of thinking about a prime number is that a number is not prime if it is divisible by a prime number (except 1). So if a vector is created of prime numbers already found, then rather than having the division loop test all odd numbers from 3 to sqrt, it just tests all numbers already inserted into the prime vector. If a prime is found, then it is inserted into the vector. For large prime numbers with a suitable initial reserve size of the vector (to reduce memory re-allocation) this can be quite fast.

PS As Eri523 and laserlight have pointed out, 1 is not a prime number. :blush: I was going to update this post before but lost internet connection whilst being upgraded to fibre. I will also amend the code.
• May 14th, 2013, 05:03 AM
Eri523
Re: Prime Numbers
Quote:

Originally Posted by 2kaud
A prime number is a number that is only divisible by itself and 1.

Please note thar 1 is not a prime, i.e. rhe "and" in your sentence is to be interpreted in the sense of common human language understanding rather than the boolean sense (sort of "exclusive and"). One consequence, for instance, of 1 being a prime would be that the count of prime factors of a number (and the sum of factors) would be indeterminate, as one could always add any number of 1 factors.

BTW, when it comes to speed, I really love the Sieve algorithm. :) ... though its memory demands may really complicate its use.
• May 14th, 2013, 05:32 AM
laserlight
Re: Prime Numbers
I was hoping that 2kaud would make the edit after replying to my PM instead of going somewhat off topic when someone else spotted the inclusion of 1 as a prime, but oh well...

Quote:

Originally Posted by Eri523
Please note thar 1 is not a prime, i.e. rhe "and" in your sentence is to be interpreted in the sense of common human language understanding rather than the boolean sense (sort of "exclusive and").

Instead of re-interpreting, it would be simpler to impose a requirement for prime numbers to be greater than 1. Perhaps more accurately than what 2kaud wrote, we could say that a prime number is a positive integer that has exactly one positive integer divisor other than 1.

Quote:

Originally Posted by Eri523
One consequence, for instance, of 1 being a prime would be that the count of prime factors of a number (and the sum of factors) would be indeterminate, as one could always add any number of 1 factors.

It might be better to just mention the fundamental theorem of arithmetic since it may not be obvious as to the signifance of such a count.

Quote:

Originally Posted by Eri523
I really love the Sieve algorithm.

There's more than one sieve algorithm for finding prime numbers ;)
• May 14th, 2013, 06:50 AM
Eri523
Re: Prime Numbers
Quote:

Originally Posted by laserlight
[...] Perhaps more accurately than what 2kaud wrote, we could say that a prime number is a positive integer that has exactly one positive integer divisor other than 1.

A pretty simple yet complete definition of primes we can perfectly settle on. :)

Quote:

It might be better to just mention the fundamental theorem of arithmetic since it may not be obvious as to the signifance of such a count.
Actually, when researching for my post, I skipped the Fundamental Theorem section right to Primality Of One and based my post on that paragraph, thereby overlooking that the Fundamental Theorem practically says almost exactly what I wanted to express, juat on a solid scientific fundament... :o That's pobably because I usually prefer practical explanations about fundamental theorems when possible. (Yeah, not a really scientific attitude, I admit... :blush: In fact, the way I memorized for myself why 1 is not a prime is even more funky: It spoils the beauty of the prime factorization algorithm by introducing an extra special case. Even though, at implementation level, that probably wouldn't ever have any efficiency impact at all...)

Quote:

There's more than one sieve algorithm for finding prime numbers ;)
Really? Cool. :) I just knew the Eratosthenes algorithm until now. Do you have a link to some overview of Sieve algorithms? May make up a nice night reading on the tablet. :D (Oh, on second sight... Please don't over-interpret that last sentence. ;))
• May 14th, 2013, 09:40 PM
rockx
Re: Prime Numbers
Now i have another problem. i have been entering pretty big numbers to calculate.....

Somehow the other, the output file i got was over 512MB .doc file, and this failed the windows from opening the file. so whats the best file format i could be saving my output so that even if it is over a 1GB, i will still be able to see the result.