プロジェクトオイラー 問題１０(project euler problem 10)

課題やっと片付いた！専攻がむずくなってきましたが、量子情報の研究室行くためにGPAしっかり維持せねば...
あっ、どうも、マツケンです。

今回の問題↓
Problem 10 - PukiWiki

<考え方>
・最近習得したアリストテレスの篩を行っていく。
・大きい配列を扱える最強のmalloc実装!
・探索範囲の削減。（詳しくはソースコード参照）<ソースコード>

/*
    The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

    Find the sum of all the primes below two million.
*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define N 2000000

int main(void){
    
    int sq_num = (int)sqrt((double)N);
    long long int sum = 0;
    int *prime;  //素数であるものに1を、そうでないものに0を対応させる配列。
    prime = (int *) malloc(sizeof(int) * N);
    clock_t start, end;

    start = clock();

    for (int i = 0; i < N; i++)
        prime[i] = 1;  //素数の候補を作るために、全ての数に1を入れる。
        prime[0] = 0;//0は素数ではない。    
        prime[1] = 0;//1は素数じゃない。

    for (int i = 2; i <= sq_num; i++) {//探索範囲の削減
        if (prime[i] == 1)          //注目している数、prime[i]が素数なら
        for (int j = i; i * j <= N; j++)//j ≧ i
            prime[i * j] = 0;  //素数の倍数は素数じゃない。
    }

    for(int i = 0; i < N; i++){
        if(prime[i] == 1) sum += i;
    }

    printf("Ans = %lld\n", sum);

    end = clock();
    printf("かかった時間%d[ms]\n", end - start);

    free(prime);
    return (0);
}

<実行結果>

Ans = 142913828922
かかった時間149[ms]

今回は見やすいかな...？