前n个素数的和

求前n个素数的和。

codepad.org已验证。

用一个数组存储至今为止已发现的素数以降低时间复杂度。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 1000

int *cache = NULL;


int isPrime(int num){
    if(num == 1 || num == 2) return 1;
    if(cache == NULL){
        cache = (int*)malloc(sizeof(int)*MAX);
        memset(cache, 0 , sizeof(int)*MAX);
        cache[0] = 2;
    }
    int i = 0;
    for(;;){
        if(cache[i]!=0){
            if(num%cache[i] == 0)
                return 0;
            else
                i++;
        }
                else{
                        cache[i] = num;
         return 1;
                }
    }
}


int primesum(int count){
    int sum = 0;
    int num = 0;
    while(count>0){
        num++;
        if(isPrime(num)){
            sum+=num;
            count--;
        }
    }
    return sum;
}

int main(){
    printf("sum = %d \n", primesum(200));
}