Prime Insight

Started by Senses777 May 20, 2002 10:53 PM

28 comments, last by Senses777 22 years, 8 months ago

Author

756

May 20, 2002 10:53 PM

I need a faster function to test for primality than my current one. It only needs to test odd numbers, and the numbers will always be greater than or equal to 11. Also, the function cannot be a sieve. The function takes in regular ints. It could also be a free online math library or posted code elsewhere, if you know a good link ^^. Does anyone have some insight on a faster one than this, or where I can find one? I have looked all over but only found algorithms for huge prime numbers ( > 10^23 or even higher) and they are *VERY* slow on the small ones I am finding. Here is what I have right now:

  
inline int Prime(int num)
{
	static int a;
	if(!(num%3)) return 0; 
	a=5;
	static int sr;
	sr=((int)sqrt(num))+1;
	while (a < sr) 
	{ 
		if(!(num%a)) 
			return 0; 
		if(!(num%(a+2))) 
			return 0; 
		a+=6; 
	} 
	return 1; 
}

.sen

"I want to make a simple MMORPG first" - Fenryl

LilBudyWizer

491

May 20, 2002 11:08 PM

All primes are 6n+/-1 except 2 and 3 which isn''t to say the converse is true.

Keys to success: Ability, ambition and opportunity.

Senses777

Author

756

May 21, 2002 01:04 PM

yes, and the function above takes advantage of that. c''mon, anyone? .sen

"I want to make a simple MMORPG first" - Fenryl

Pouya

869

May 21, 2002 03:30 PM

Checking if a number is prime or not is an NP-complete problem. Meanining that there is currently no known way of doing it efficiently, but it''s proven that there is some way (most likely not with our turing machine model)

TerranFury

142

May 21, 2002 03:40 PM

There are many tests which can definately tell you if something is NOT a prime number. Using these will provide an early exit with many numbers. However, verifying that a number that passes all the tests is certainly prime remains an NP complete problem.

[edited by - TerranFury on May 21, 2002 4:49:26 PM]

Senses777

Author

756

May 21, 2002 04:03 PM

what does NP-complete mean, and I just need a faster algo than I am using now. .sen

"I want to make a simple MMORPG first" - Fenryl

Eric

138

May 21, 2002 10:35 PM

For the values of a in your loop, instead of
a <= 6*n +/- 1,
do
a <= primes[n],
where primes is a pre-computed array of primes up to sqrt(INT_MAX) ~= 50,000 (I''m assuming your largest possible input is INT_MAX). There are about 5000 primes in this range. For input values less than 50,000, you can just binary-search the primes array directly.

If your largest possible input is significantly less than INT_MAX, you might consider just precomputing the whole range. The array would probably be in the tens to hundreds of MB''s range.

Regarding "NP-complete" and "no known way of doing it efficiently"... an "efficient" algorithm generally implies one that runs in polynomial time. "NP-complete" means that, were you to actually find a polynomial-time solution to this problem, you would be hailed as a god by computer scientists everywhere.

Anonymous

May 22, 2002 05:44 AM

You can use a Monte-Carlo algorithm to check primality.

The basic idea is that you check for division by random numbers, with each number tested, the chances of your testee number being prime rise.

I forget the details, but I seem to remember being told that after about 50 tests, you are more likely to get a false result through cosmic rays flipping bits on your CPU than the algorithm choosing the wrong numbers to test