Prime Numbers
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member
Join Date
May 2004
Posts
249

## 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.

2. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,734

## Re: Prime Numbers

Use a better or more appropriate algorithm, e.g., the sieve of Eratosthenes may be applicable.

3. ## Re: Prime Numbers

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?

4. ## 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.

5. Member
Join Date
May 2004
Posts
249

## 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");

}```

6. ## Re: Prime Numbers

Try this. I've kept your code structure but just made a couple of changes. 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;
}```
Last edited by 2kaud; May 14th, 2013 at 07:50 AM. Reason: Minor optimise change to algorithm / 1 is not a prime number

7. Member
Join Date
May 2004
Posts
249

## Re: Prime Numbers

Originally Posted by 2kaud
Try this. I've kept your code structure but just made a couple of changes. 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;
}```
I have got another question. the above code simply works fine. but is there any other way possible to further modify this

This particular line does what its supposed to do:
Code:
`if (i % j == 0)`
however, is there any way possible to replace 'j' wtih all the numbers that have actually been generated?

8. ## Re: Prime Numbers

Originally Posted by rockx
I have got another question. the above code simply works fine. but is there any other way possible to further modify this
Of course there is. Prime number generation is one of the most-researched subjects in computer sciences and mathematics, so there's plenty of other variations out there to study.

This particular line does what its supposed to do:
Code:
`if (i % j == 0)`
however, is there any way possible to replace 'j' wtih all the numbers that have actually been generated?
What are you asking for? j already is being replaced with all candidate numbers to check for being an integral divider, time-sequentially within the loop.

9. Member
Join Date
May 2004
Posts
249

## 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

10. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

## Re: Prime Numbers

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.

11. ## 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. I was going to update this post before but lost internet connection whilst being upgraded to fibre. I will also amend the code.
Last edited by 2kaud; May 14th, 2013 at 07:49 AM. Reason: 1 is not a prime number

12. ## Re: Prime Numbers

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.

13. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,734

## 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...

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.

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.

Originally Posted by Eri523
I really love the Sieve algorithm.
There's more than one sieve algorithm for finding prime numbers

14. ## Re: Prime Numbers

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.

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... That's pobably because I usually prefer practical explanations about fundamental theorems when possible. (Yeah, not a really scientific attitude, I admit... 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...)

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. (Oh, on second sight... Please don't over-interpret that last sentence. )

15. Member
Join Date
May 2004
Posts
249

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•