YoungProgrammer

Back to Problem list

Problem 29: 
If a number is the only number between a prime number and a square number it is beprisque.
How many positive beprisque numbers exist with less than 5 digits?


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

int isPrime(int n) {
    int i;
    if(n ==1) return 0; // 1 is not prime
    if(n == 2) return 1; // 2 is prime
    if(n%2 == 0) return 0; // even numbers are not prime except 2
    for(i = 3; i*i<=n; i+=2) { // has any divisors ?
        if(n%i == 0) return 0;
    }
    return 1;
}

int isSquare(int n) { // think when n = 9 and when n = 15, you will able to find the logic.
    int k = (int)sqrt(n);
    return k*k == n; 
}

int isBeprisque(int n) {
    if(isPrime(n+1) && isSquare(n-1)) return 1;
    if(isPrime(n-1) && isSquare(n+1)) return 1;
    return 0;    
}

int Count() {
    int i, total = 0;
    for(i = 2; i<10000; i++) {
        if(isBeprisque(i)) {
                //printf("%d ",i); // u can print these numbers
                total++;
        }
    }
    return total;
}
int main() {
    printf("%d\n",Count());
    return 0;
}

Back to Problem list