Thread: calculating if a number is a prime number or not

1. calculating if a number is a prime number or not

i found on the internet a formula that said if the result of 6n+1 or 6n-1 is a natural number where n is the number you wish to check the n must be prime
ie 7 - 1 = 6/6 = 1 7 is prime.

carrying this forward lets take the number 13195 the above states its a prime number. which is wrong

question is rather than checking every number from 2 to n how do you calculate a prime  Reply With Quote

2. There is no known way to calculate primes; there are just sophisticated ways to prove that a number is prime, and ways that prove that a number is a composite so well that they can be used just a few times to determine that a number is probably a prime.  Reply With Quote

3. so one has to work their way through n/n-1....... n/2  Reply With Quote

4. No, a basic brute force algorithm only needs to test the possible prime divisors from 2 up to and including the square root of the number on question.  Reply With Quote

5. Originally Posted by laserlight No, a basic brute force algorithm only needs to test the possible prime divisors from 2 up to and including the square root of the number on question.
Yep... and you can tweak a little to speed things up: The only even prime is 2, so, you must test the value only against odd numbers less then or equal to the square root.  Reply With Quote

6. Originally Posted by flp1969
you can tweak a little to speed things up: The only even prime is 2, so, you must test the value only against odd numbers less then or equal to the square root
Testing against odd numbers is going to be slower than testing against prime numbers The problem is getting the prime numbers to test with in the first place, e.g., a sieve to get a list of primes to test just one number that turns out to be composite might be a waste.  Reply With Quote

7. Originally Posted by flp1969 Yep... and you can tweak a little to speed things up: The only even prime is 2, so, you must test the value only against odd numbers less then or equal to the square root.
isnt there a algorithm that shifts,so you can extend it to rule out 4,8,16,32,64,128,256... + some combinations of those bits ==nonprimes?  Reply With Quote

8. Originally Posted by laserlight Testing against odd numbers is going to be slower than testing against prime numbers The problem is getting the prime numbers to test with in the first place, e.g., a sieve to get a list of primes to test just one number that turns out to be composite might be a waste.
Sieve of Erastotenes: Speeding up things a lot more, for "small" values.
But sorta of impractical to use a huge array to test a big 64 bits (or 128 bits) value.   Reply With Quote

9. Originally Posted by laserlight No, a basic brute force algorithm only needs to test the possible prime divisors from 2 up to and including the square root of the number on question.
where does one get the prime numbers to divide by though. it all seems a little chicken and egg to me
lets say i want to find the 100th prime number i have to count from two to x ^1/2 (sq root of an unknown number) dividing by all the primes already found. for a small number the list is small but as the list grows the amount of divisions grows by the number in the list. ie to find the 100th i would have to divide each number from the 99th prime to the 100th 99 times  Reply With Quote

10. Erastothenes was a big old chicken...
Sieve of Erastothenes  Reply With Quote

11. Originally Posted by flp1969 Erastothenes was a big old chicken...
Sieve of Erastothenes
thanks,if he lived today seems he had used truth tables and statistics to find a pattern of where primes are compared to the other numbers

huge array as in a filled 4TB drive? compile into 64bit faster when reaching really big numbers over max 32bit int?  Reply With Quote

12. If you want something fast, heavy on the maths, and not entirely 100% accurate (it's probabilistic), then
Miller–Rabin primality test - Wikipedia

But if you're already using GMP, you're in luck.
GNU MP 6.1.2: Prime Testing Algorithm  Reply With Quote

13. Originally Posted by laserlight No, a basic brute force algorithm only needs to test the possible prime divisors from 2 up to and including the square root of the number on question.
its interesting to see how fast brute force is going to be compared to other algos
how do you mean by square root?,excluding numbers that endsup sqrt(100)=10.0,sqrt(25)=5.0... ?

@Salem,thanks  Reply With Quote

14. i think that to evaluate if 100 is a prime or not you don't need to check past the square root of 100 because anything past 10 will be a multiple of a prime  Reply With Quote

15. Originally Posted by I C everything how do you mean by square root?,excluding numbers that endsup sqrt(100)=10.0,sqrt(25)=5.0... ?
Excluding tests against values above sqrt(N).

Two of the greatest values multiplied which will give N are a*a=N, or a=sqrt(N). So, if you test N against values greater then 'a' you are "re-testing" values already tested, since a*b=b*a (remember that a and b are integers)... For exemple: 12 = 1*12 = 2*6 = 3*4 = 4*3 = 6*2 = 12*1... You only need to test N (12) against 1, 2 and 3 only...  Reply With Quote

Popular pages Recent additions calculate, forward, number, prime, states 