I think brewbuck implemented Rabin-Miller, which is probabilistic and hence might return results that fail abachler's contest requirements.Quote:

Originally Posted byzacs7

Printable View

- 12-02-2008laserlightQuote:

Originally Posted by**zacs7**

- 12-02-2008zacs7
What a cheat :-), oh well... just pick one of those values for the test and give him a big fat zero.

- 12-02-2008laserlightQuote:

Originally Posted by**zacs7**

In a way, this is similiar to the requirements of cryptographic algorithms that need large primes (say, produce any 2 primes that meet the size requirements, as fast as possible), hence the choice of the same commonly used algorithm is natural, in retrospect. - 12-02-2008abachler
yes, both CUDA and OpenMP are available. Please specify which of cuda.lib or cudart.lib your submission requires. OpenMP is limited to version 2.0 as thats what 2008 supports.

ah, i see now, so basically he is using a non-deterministic approach. If a number fails the test it is definately NOT prime (spectacular failure), but if it passes you cant be 100% sure that it IS prime (unconvincing success). This is an acceptable optimization since it could be applied as a definitive test to weed out many strong pseudo primes. It could then be made comprehensive by applying the modified Sieve of Eratosthenes in the base code. So we run the computationally inexpensive test first and only if it fails to prove a number composite do we apply the expensive test. Although I think i will perhaps switch to AKS for the verification routine. - 12-02-2008Sfel
Here's mine. I hope I didn't break any rules; according to the first post I should have only one function, and I have 2 (+main). If it needs any modifications to be accepted let me know.

Runs in 0.3 secs on my comp.

According to my tests it's correct. If it doesn't work for you in any way, I can try again right? :) - 12-02-2008brewbuck
I tuned the constant 'k' for performance at the risk of getting bad primes. Then I crossed my fingers and hoped abachler's rand() function didn't suck.

Quote:

In a way, this is similiar to the requirements of cryptographic algorithms that need large primes (say, produce any 2 primes that meet the size requirements, as fast as possible), hence the choice of the same commonly used algorithm is natural, in retrospect.

- 12-02-2008abachler
Well, its not so much that it is 'good enough' as it's 'the best they have'. Cryptosystems typically use primes that are at least 2^128 and typically as high as 2^2048 and some international banks use primes greater than 4096 bits. I believe there are commercial(restricted) systems available in the 16K bit range. Obviously these primes can never be deterministically proven prime by checking all possible prime factors, at least not with current computers. Generally even if these numbers arent prime, its good enough that they are not trivially factorable.

I think you can actually reduce k further by choosing specific values forCode:`a = {2 , 7, 61 }`

- 12-03-2008abachler
I think Sfel did even better ...

- 12-04-2008Sfel
For those who are interested in the method, I used the sieve of eratosthenes in the following way:

1. Figure out a maximum range (hi) such that the interval [lo = 2^31 + 1, hi] contains at least 100 000 primes.

2. Generate prime numbers (using the sieve) up to sqrt(hi)

3. For each of these primes, find its lowest multiple which is >= lo. Starting from that, mark all its multiples which are <= hi as not prime.

4. All the numbers in the interval [lo, hi] that are not marked as not prime are definitely prime.

So basically, the trick is figuring out how to generalize the sieve of eratosthenes to work for any interval [a,b].

The only disadvantage would be the memory used (I think I use about 2 megs for one of the x arrays), so if you were to ask for, say, a million primes, I'd probably have to resort to using bitsets or bitwise operations to lower used memory. - 12-04-2008laserlightQuote:

Originally Posted by**Sfel**

- 12-05-2008Akkernight
Is it hard to make an algorithm for prime numbers o.O? I know this dude in Gmod who made one using Wire... Didn't look comlicated at all :P

Oh and I guess 1991 is a prime number! Or was it 1993... - 12-05-2008laserlightQuote:

Originally Posted by**Akkernight**

Quote:

Originally Posted by**Akkernight**

- 12-05-2008abachler
so was 2003 and the next one will be 2011, but then so is 18446744073709551557

there is a rather broad line between numerical analysis and numerology. - 12-06-2008IceDane
It was my intention to participate in this challenge, so I whipped up a modified version of the Sieve of Eratosthenes, where one byte represents 8 numbers. However, I have had some trouble making the code work in a specified range, but I haven't taken the time to look at it properly.

It can primes ranging from 1 to 80 million or so in a matter of seconds so far, I'll just have to see if I can get it to work properly. - 12-06-2008abachler
The smaller numbers (under 2^32) are generally very easy to prove prime or composite. 64 bit numbers are much slower, both because the math takes twice the bandwidth per variable, and because the proofs themselves are more expensive.