Is this a new Primality Test?

296 Views Asked by At

Every $n \in \mathbb{Z}$ is prime if all lattice points on $x+y=n$ are visible from the origin.

Graphed points on $x+y=n$ not visible from the origin for potential primes.

8x8 raster image

// 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>


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


int isPrimeNumber(uint64_t n)
{
    if (n == 1) return 0;
    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;
}


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

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

    return 0;
}
1

There are 1 best solutions below

0
On BEST ANSWER

If $n=ab$ with $a$ and $b$ greater than $1$ then $$ n = a + a(b-1) $$ so $(a, a(b-1))$ is a point on the line.

That says that there are invisible points when $n$ is composite.

Conversely, if $n$ is prime and $n=x+y$ then any common divisor of $x$ and $y$ will divide $n$, so $(x,y)$ is visible.

So this is a valid primality test.

It's not an efficient test.