# Need a fast way to get a lot of "primzahlen"(german) numbers that can be divided only by 1 and itself.

This is my first try:
const AnzPrimz = 10000;
bool Primzahl;
int Primzahlen[AnzPrimz];
int ArrayIndex = 0;

for(int i=3; (ArrayIndex < AnzPrimz) && (i < 64000); i = i+2)
{
Primzahl = true;
for(int j=2; (j <= i/2) && Primzahl; j++)
{

if((i % j) == 0)
{
Primzahl = false;
}
}
if(Primzahl)
{
Primzahlen[ArrayIndex] = i;
ArrayIndex++;
}
}
How can I do this faster?
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Author Commented:
Edited text of question.
0
Commented:
Primzahlen = Prime Numbers

What you've posted is called the Sieve of Erastothenes and is a classic way of testing numbers for "primeness".  It's problem is that it is slow.

This is an area of much research as finding large prime numbers is a key component in many crypto systems.

You might try searching the web for the terms "prime number", "factoring", "cryptography", "encryption".
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
this is not the sieve of erastothenes... it's the test every odd number method...

if u wanna find ALL the primes from 1 to n i think the easiest & ok-ly fast way IS SoE... it's the 'cross-out' the multiples of prime method...
0
Commented:
lychee,

Yes, you are correct, I didn't look closely enough at the code...
0
Commented:
noprob... i'm really interested in how to find large prime numbers fast tho...
0
Commented:
> How can I do this faster?

There's several things you can do to make your code faster. First, you're not considering even numbers. So, why are you dividing by 2?

Also, since you're not considering even numbers, there's no reason to consider even divisors. That's because any number, even or odd, when multiplied by an even number, results in an even number.

Next, to see if i is prime, you're searching from 2 to i/2. That's too many tests; you should stop searching at sqrt(i). A number has no integer factors larger than its square root.

Here's your code with those optimizations:

for(int i=3; (ArrayIndex < AnzPrimz) && (i < 64000); i = i+2)
{
Primzahl = true;
int nStop = sqrt(i);
for(int j=3; (j <= nStop) && Primzahl; j += 2)
{
if((i % j) == 0)
{
Primzahl = false;
}
}

if(Primzahl)
{
Primzahlen[ArrayIndex] = i;
ArrayIndex++;
}
}

The optimizations I've made seem subtle, but they're quite expensive. You've gone from an O(n*n/2) algorithm to an O(n/2 * sqrt(n)/2) algorithm. For n = 64000, that's 505 times more performant!

If you're only looking for numbers from 1 thru 64000, then the Sieve of Erastothones is fast enough. For much larger numbers, it ends up using way too much memory and brute-force testing (what you're doing) is actually faster because the Seive inherently has very poor data locality.

..B ekiM
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.