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?
SirSmokeALotAsked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
jhanceConnect With a Mentor 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
 
SirSmokeALotAuthor Commented:
Edited text of question.
0
 
_lychee_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
Never miss a deadline with monday.com

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

 
jhanceCommented:
lychee,

Yes, you are correct, I didn't look closely enough at the code...
0
 
_lychee_Commented:
noprob... i'm really interested in how to find large prime numbers fast tho...
0
 
mikeblasCommented:
> 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
All Courses

From novice to tech pro — start learning today.