# Thread: Prime numbers

1. Originally Posted by execute
That would not make it any faster. I timed it.
Odd numbers are faster up to the sqrt of the function is the best way.
As long as your prime numbers fit in the L1 (or L2) cache of the processor, it's faster to test only prime numbers, because only roughly one in three odd numbers is a prime (one in three odd numbers is divisible by 3, and only one of the other two are most of the time a prime), and reading an one value out of an array and dividing by that is quicker than performing two divide operations on ALL modern processors.

If you have a HUGE number of primes, then it's better to continue from the largest that fits in the cache with every other number, since just incrementing a number is faster than reading from the memory outside of the processor.

--
Mats

2. I suppose so, I never thought of using that method, and I doubt anyone would require that sort of intensive coding for any standard prime number involving project :P. Good job on whoever thought of it.

3. Soma u so craycee. u maked me laffing my arse uff. U can reed sum info on da wikipedia 4 algorithms of primes.

4. This is correct, that's what I meant by fastest, didn't know anyone would use that sort of method.
This is a sieve. It is a slow sieve. The complexity guarantees that the more primes you need the slower it will be compared to many other prime sieves.

Why are you spamming phantom?
I wasn't. It was wishful thinking...

U can reed sum info on da wikipedia 4 algorithms of primes.
You use AOL don't you?

I suggest you both benchmark this against a standard implementation of "Sieve of Erastothenes" with sets sizes of 10, 100, 1000, and 10,000.

Soma

5. But da prime sleave uses a lots of memories.

6. I'd rather not have a pointless debate about what a Sieve is or is not in terms of programming.
But I believe it's used for TEA!

The algorithm I talked about was the fastest available for most average programmers (I wasn't trying to say that no one can make faster) that is not using the complex L1/L2 cache method.

7. Before you guys get too excited, look again: whiterebbit is working on a problem that involves finding the largest prime factor, not finding if the number is prime (though coincidentally a prime is its largest prime factor). Just coming up with a primality testing algorithm is not enough (though a prime factoring algorithm will certainly work).

Popular pages Recent additions