4
\$\begingroup\$

I devised a new primality test isPrimeNumber() below which determines if 1000000007 is prime. It works fine but the code looks unprofessional in my opinion. Is there any way to refactor it to make it more readable? Maybe inline the recursive gcd() function so everything is self-contained in the isPrimeNumber() function etc.,...? Any tips? Thanks!

// Primality Test
// Every n is prime if all lattice points on x+y=n are visible from the origin.

#include <stdio.h>
#include <stdint.h>
#include <math.h>

#define NOT_PRIME_NUMBER 0
#define PRIME_NUMBER 1


uint64_t gcd(uint64_t a, uint64_t b)
{
    return (b != 0) ? gcd(b, a % b) : a;
}


int isPrimeNumber(uint64_t n)
{
    if (n == 2 || n == 3 || n == 5)
    {
        return PRIME_NUMBER;
    }
    
    uint64_t m = n % 10;

    if (m == 1 || m == 3 || m == 7 || m == 9)
    {
        uint64_t x, y;
        uint64_t step = 0, maxStep = sqrt(n) / 2;

        // Start near line x=y.
        x = (n / 2) + 2;
        y = n - x;

        do {

            // Check lattice point visibility...
            if (gcd(x, y) != 1)
            {
                return NOT_PRIME_NUMBER;
            }

            x++; y--; step++;

        } while (step < maxStep);
    }
    else
    {
        return NOT_PRIME_NUMBER;
    }

    return PRIME_NUMBER;
}


int main(int argc, char* argv)
{
    uint64_t n = 1000000007;

    if (isPrimeNumber(n) == PRIME_NUMBER)
    {
        printf("%llu prime.", n);
    }
    else
    {
        printf("%llu not prime.", n);
    }

    return 0;
}
\$\endgroup\$
2
\$\begingroup\$

Your m digit checking can be simplified and your do while loop can be replaced with the simpler for loop. The constants also seem excessive given that non-zero truthiness is baked into C.

int isPrimeNumber(uint64_t n)
{
    if (n==2 || n==3) return 1;
    if (n%2==0) return 0;
    
    // Start near line x=y.
    uint64_t x = (n / 2) + 2;
    uint64_t y = n - x;

    uint64_t count = sqrt(n) / 2;
    for (uint64_t i=0;i<count;++i) {
        // Check lattice point visibility...
        if (gcd(x, y) != 1) return 0;

        x++; y--;
    }

    return 1;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Looks great! The only missing case is when n=1. Maybe we could add a check here: if (n == 1) return 0; if (n == 2 || n == 3) return 1; if (n % 2 == 0) return 0; .... or maybe somekind of c-ternary-operator? \$\endgroup\$
    – vengy
    Jan 10 at 13:00
2
\$\begingroup\$

Avoid FP functions for integer problems.

sqrt(n) problems include potential inexact roots for perfect squares (it is a FP function, not an integer one) and rounding of the double argument when n > 254 or so.

Sample alternative; int_sqrt in C


Other: Only small stuff:

Minor: OK for a narrower type

//uint64_t m = n % 10;
unsigned m = n % 10u;
if (m == 1 || m == 3 || m == 7 || m == 9)

Minor: Streamline first test

Rather than 3 initial tests that are rarely true, maybe one.

//if (n == 2 || n == 3 || n == 5) {
//    return PRIME_NUMBER;
//}
if (n <= 6) {
  return (n == 2 || n == 3 || n == 5) ? PRIME_NUMBER : NOT_PRIME_NUMBER;

Minor: potential mis-matched type and specifier

"%llu" matches a unsigned long long.

"%" PRIu64 (from <inttypes.h>) matches a uint64_t.

Today, it is common unsigned long long and uint64_t are the same type. But that is not specified. unsigned long long may be wider.

Alternative:

int main(void) {
  uint64_t n = 1000000007;
  if (isPrimeNumber(n) == PRIME_NUMBER) {
    // printf("%llu prime.", n);
    printf("%llu prime.", (unsigned long long) n);
    // OR
    printf("%" PRIu64 " prime.", n);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.