I am writing a program to read an integer n (0 < n <= 150) and find the smallest prime p and consecutive prime q such that q - p >= n.

My code works, but it runs for about 10 seconds for larger n.

#include <stdio.h>
#include <stdlib.h>

int isPrimeRecursive(int x, int i){
    if (x <= 2){
        return (x == 2 ? 1:0);
    }
    if (x % i == 0){
        return 0;
    }
    
    if (i * i > x){
        return 1;
    }
    return isPrimeRecursive(x, i 1);
}

int findSuccessivePrime(int x){
    while (1){
        x  ;
        if (isPrimeRecursive(x, 2)){
            return x;
        }
    }
    return 0;
}

int findGoodGap(int n, int *arr){
    int prime = findSuccessivePrime(n*n);
    
    while (1){
        int gap;
        int succPrime;
        succPrime = findSuccessivePrime(prime);
        gap = succPrime - prime;
        if (gap >= n){
            arr[0] = succPrime;
            arr[1] = prime;
            return gap;
        }
        prime = succPrime;
    }
    return 0;
}

int main(int argc, char *argv[]){
    int n;
    int arr[2];
    scanf("%d", &n);
    int goodGap;
    goodGap = findGoodGap(n, arr);
    
    printf("%d-%d=%d\n", arr[0], arr[1], goodGap);
    
    return 0;
}

How can I make the program more efficient? I can only use stdio.h and stdlib.h.

CodePudding user response：

The algorithm is very inefficient. You're recalculating the same stuff over and over again. You could do like this:

int n;
// Input n somehow
int *p = malloc(n * sizeof *p);

for(int i=0; i<n; i  ) p[i] = 1; // Start with assumption that all numbers are primes

p[0]=p[1]=0; // 0 and 1 are not primes

for(int i=2; i<n; i  ) 
    for(int j=i*2; j<n; j =i) p[j] = 0;

Now, p[i] can be treated as a boolean that tells if i is a prime or not.

The above can be optimized further. For instance, it's quite pointless to remove all numbers divisible by 4 when you have already removed all that are divisible by 2. It's a quite easy mod:

for(int i=2; i<n; i  ) {
    while(i<n && !p[i]) i  ; // Fast forward to next prime

    for(int j=i*2; j<n; j =i) p[j] = 0;
}

As Yom B mentioned in comments, this is a kind of memozation pattern where you store result for later use, so that we don't have to recalculate everything. But it takes it even further with dynamic programming which basically means using memozation as a part of the algorithm itself.

An example of pure memozation, that's heavily used in the C64 demo scene, is precalculating value tables for trigonometric functions. Even simple multiplication tables are used, since the C64 processor is MUCH slower at multiplication than a simple lookup. A drawback is higher memory usage, which is a big concern on old machines.

CodePudding user response：

I think it would be a good approach to have all of the prime numbers found and store it in an array; in that case you wouldn't need to do divisions from scratch to find out whether a number is a prime number or not

This is the algorithm which checks if the number "n" is prime simply by doing divisions

bool isPrime(int n) {
    if(n <= 1) return false;
    if(n < 4) return true;
    if(n % 2 == 0) return false;
    if(n < 9) return true;
    if(n % 3 == 0) return false;

    int counter = 1;
    int limit = 0;
    while(limit * limit <= n) {
        limit = limit * 6;
        if(n % (limit   1) == 0) return false;
        if(n % (limit - 1) == 0) return false;
    }

    return true;
}

If you use the algorithm above which its time complexity is in order of sqrt(n) , your overall time complexity would be more than n^2

I suggest you to use "Sieve of Eratosthenes" algorithm to store prime numbers in an array

Check out this link https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Here is the code. I used optimized sieve in Main function.

#include <iostream>
using namespace std;

void Sieve(bool* list, const int n);
void OptimizedSieve(bool* list, const int n);

int main() {
    bool list[100 / 2];
    for(int i = 0; i < 100 / 2; i  ) list[i] = true;
    OptimizedSieve(list, 100 / 2);

    for(int i = 0; i < 100 / 2; i  ){
        if(list[i]) cout << (2 * i)   1 << endl;
    }
    return 0;
}

void Sieve(bool* list, const int n){
    list[0] = false;
    list[1] = false;

    for(int p = 2; p * p <= n; p  ){
        if(!list[p]) continue;
        for(int j = p * p; j < n; j  = p){
            if(list[j] == true) list[j] = false;
        }
    }
}

void OptimizedSieve(bool* list, const int n){
    list[0] = false;
    for(int p = 3; p * p <= n; p  = 2){
        if(!list[(2 * p)   1]) continue;
        for(int j = p * p; j <= n; j  = 2 * p){
            int index = (j - 1) / 2;
            if(list[index]) list[index] = false;
        }
    }
}