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
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
so one has to work their way through n/n-1....... n/2
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.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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.
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.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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?
you tell me you can C,why dont you C your own bugs?
Sieve of Erastotenes: Speeding up things a lot more, for "small" values.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.
But sorta of impractical to use a huge array to test a big 64 bits (or 128 bits) value.
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
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?
Last edited by I C everything; 06-06-2019 at 08:03 AM.
you tell me you can C,why dont you C your own bugs?
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
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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
you tell me you can C,why dont you C your own bugs?
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
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...
