Thread: greatest common divisor is a prime number (pairs of numbers problem in C)

  1. #31
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,914
    Quote Originally Posted by flp1969
    This is essentially the same routine I posted before, except you check for divisors by 3 in the beginning (starting the checks in the loop, for divisors by 5)...
    No, it is not the same: your routine makes use of the fact that all primes greater than 2 are of the form 2k+1; this routine makes use of the fact that all primes greater than 3 are of the forms 6k-1 or 6k+1. On average, this routine makes two-thirds as many checks for divisibility.

    Quote Originally Posted by flp1969
    A better way, which can consume a lot of memory, is to check for the previously found primes less or equal to the square rooot of n...
    That's what I wrote in post #25. I think it was the approach I took some years (over a decade?) back when someone posted some primality testing challenge here, but my solution wasn't very good compared with some others as it wasn't tailored to the challenge.
    Last edited by laserlight; 10-29-2019 at 03:11 PM.
    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

  2. #32
    Registered User
    Join Date
    Feb 2019
    Posts
    717
    Quote Originally Posted by laserlight View Post
    No, it is not the same: your routine makes use of the fact that all primes greater than 2 are of the form 2k+1; this routine makes use of the fact that all primes greater than 3 are of the forms 6k-1 or 6k+1. On average, this routine makes two-thirds as many checks for divisibility.
    I see... but nobody, until now, proved if this is correct... I have my doubts...

  3. #33
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,914
    Quote Originally Posted by flp1969 View Post
    I see... but nobody, until now, proved if this is correct... I have my doubts...
    Refer to my post #20 at the end. I've demonstrated that it is mathematically correct.

    To make it easier:
    Quote Originally Posted by laserlight
    We could observe that any integer >= 6 could be expressed in the form 6k+0, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5, for some integer k > 0. Clearly, 6k+0, 6k+2, and 6k+4 are divisible by 2, and hence cannot be prime. 6k+3 is divisible by 3, and hence cannot be prime. Therefore, only those of the form 6k+1 and 6k+5 could be prime, i.e., if an integer >= 6 is prime, it must be of one of these two forms. But 6k+5 is congruent to 6k-1 under modulo 6, hence the statement expresses this as 6k+-1. Furthermore, 5 is also prime yet is in the form 6k-1, hence the range was specified as being > 3 rather than >= 6.
    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

  4. #34
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,784
    Quote Originally Posted by flp1969 View Post
    I see... but nobody, until now, proved if this is correct... I have my doubts...
    Well, I don't know where there is a formal proof but it's mentioned on the Wikipedia page (Primality test - Wikipedia)
    The algorithm can be improved further by observing that all primes greater than 6 are of the form 6k 1.

  5. #35

  6. #36
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    174
    Quote Originally Posted by Hodor View Post
    Well, I don't know where there is a formal proof but it's mentioned on the Wikipedia page (Primality test - Wikipedia)
    Here's an interesting result. Another way to state the 6x +- 1 identity: the square of any prime (> 3) minus one is always a multiple of 24.
    Last edited by Sir Galahad; 10-29-2019 at 11:11 PM.
    The power of null.

  7. #37
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    174
    Quote Originally Posted by laserlight View Post
    flp1969: following your example from post #16, we're probably looking at something along these lines:
    Code:
    int isPrime(unsigned int n)
    {
        if (n < 2)
            return 0;
        if (n <= 3)
            return 1;
        if (n % 2 == 0 || n % 3 == 0)
            return 0;
    
        unsigned int sqrt_ = (unsigned int)sqrt(n);
    
        // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
        for (unsigned int i = 5; i <= sqrt_; i += 4) // +4 because +2 in the loop body
        {
            if (n % i == 0)
                return 0;
            i += 2
            if (n % i == 0)
                return 0;
        }
        return 1;
    }
    I guess it's also possible to construct this more carefully with a check for the square root after each modulo test, but the idea remains the same: we're skipping numbers with an alternating +4 instead of always doing +2 (or +1) because we know that the possible prime factors to test with are of those two forms.
    Impressive! Much more efficient than the standard approach. I also like the fact that you chose to test mod 2 and 3 rather than 6. Way less cryptic.
    The power of null.

  8. #38
    Registered User
    Join Date
    May 2009
    Posts
    3,877
    Code:
        // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
        for (unsigned int i = 5; i <= sqrt_; i += 4) // +4 because +2 in the loop body
        {
            if (n % i == 0)
                return 0;
            i += 2
            if (n % i == 0)
                return 0;
        }
    Should not the for loop be like below?

    Code:
        // We only need to check divisors of the forms 6k-1 and 6k+1, for k > 0
        for (unsigned int i = 6; (i-1) <= sqrt_; i += 6)
        {
            if (n % (i-1) == 0)
                return 0;
            if (n % (i+1) == 0)
                return 0;
        }
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  9. #39
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,914
    Quote Originally Posted by stahta01
    Should not the for loop be like below?
    You could do that, but it could end up with three additions or subtractions (4, but 1 is repeated) per iteration instead of two.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. code for getting the GCD (greatest common divisor)
    By Noobpoint in forum C Programming
    Replies: 1
    Last Post: 03-07-2012, 07:13 AM
  2. The greatest common divisor (GCD) help..
    By damha in forum C Programming
    Replies: 4
    Last Post: 04-09-2011, 05:18 AM
  3. Greatest Common Divisor.....
    By muran_pling in forum C++ Programming
    Replies: 10
    Last Post: 12-18-2006, 05:02 AM
  4. Greatest Common Divisor problem
    By fenixataris182 in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 07:55 PM
  5. Greatest common divisor
    By wiz23 in forum C++ Programming
    Replies: 5
    Last Post: 04-13-2005, 04:50 PM

Tags for this Thread