The revolutionary project management tool is here! Plan visually with a single glance and make sure your projects get done.

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?

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?

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

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

All Courses

From novice to tech pro — start learning today.

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