Ir para o conteúdo

Primalidade dos números 2n^2-1 (Euler 216)

Nota: Considere os números \(t(n)\) da forma \(t(n)=2n^2-1\) onde \(n>1\). Os primeiros números do género são 7, 17, 31, 49, 71, 97, 127 e 161. Constata-se que apenas \(49=7*7\) e \(161=7*23\) não são primos. Para \(n\leq10000\) existem 2202 números \(t(n)\) que são primos.

Quantos números \(t(n)\) são primos para \(n\leq50~000~000\)?

in Project Euler, problem 216

#include <stdio.h>
#include <tgmath.h>

#define MAX 50000000

short isPrime(unsigned long n) {
    int i;
    for(i=2; i<=(unsigned long) trunc(sqrt((double) n)); ++i)
        if (n % i == 0) return 0;
    return 1;
}

unsigned long t(unsigned long n){
    return 2 * n*n - 1;
}

int main(void) {
    unsigned long i, count=0;
    for(i=2; i<=MAX; ++i)
        if (isPrime(t(i)))
            ++count;
    printf("%lu", count);
    return 0;
}