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

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    650

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,844
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    so one has to work their way through n/n-1....... n/2

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,844
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Feb 2019
    Posts
    359
    Quote Originally Posted by laserlight View Post
    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.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,844
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    56
    Quote Originally Posted by flp1969 View Post
    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?
    How do you know when you are a Guru?
    When you can (code) C even blindfolded

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    359
    Quote Originally Posted by laserlight View Post
    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.

  9. #9
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    Quote Originally Posted by laserlight View Post
    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

  10. #10
    Registered User
    Join Date
    Feb 2019
    Posts
    359
    Erastothenes was a big old chicken...
    Sieve of Erastothenes

  11. #11
    Registered User
    Join Date
    Apr 2019
    Posts
    56
    Quote Originally Posted by flp1969 View Post
    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; 1 Week Ago at 08:03 AM.
    How do you know when you are a Guru?
    When you can (code) C even blindfolded

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,213
    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.

  13. #13
    Registered User
    Join Date
    Apr 2019
    Posts
    56
    Quote Originally Posted by laserlight View Post
    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
    How do you know when you are a Guru?
    When you can (code) C even blindfolded

  14. #14
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    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

  15. #15
    Registered User
    Join Date
    Feb 2019
    Posts
    359
    Quote Originally Posted by I C everything View Post
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating the nth prime number
    By joshlete in forum C Programming
    Replies: 11
    Last Post: 05-10-2017, 02:34 PM
  2. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  3. largest number prime number that can be produced...
    By ElemenT.usha in forum C Programming
    Replies: 8
    Last Post: 02-17-2008, 01:44 AM
  4. Calculating next prime number
    By anilemon in forum C Programming
    Replies: 8
    Last Post: 04-17-2006, 10:38 AM
  5. Replies: 3
    Last Post: 03-29-2005, 04:24 PM

Tags for this Thread