[Project Euler] Problem 010

<Java>

public class Problem010 {
    private static final int LIMIT = 2000000;
    
    public static void main(String[] args) {
        System.out.println(run());
    }
    
    public static long sieve() {
        int div = 2;
        long sum = 0;
        int num = 2;
        int idx = 0;
        int[] arr = new int[LIMIT - 1];
        
        for(int i = 0; i < arr.length; ++i) {
            arr[i] = num;
            num += 1;
        }
        
        while((div*div) < LIMIT) {
            //배수 삭제
            for(int i = 0; i < arr.length; ++i) {
                if(((arr[i]%div) == 0) && (arr[i] > div)) {
                    arr[i] = 0;
                }
            }
                        
            //div에 다음 소수 대입
            for(int i = (idx + 1); i < arr.length; ++i) {
                if((arr[i] != 0) && (arr[i] > div)) {
                    div = arr[i];
                    idx = i;
                    break;
                }
            }
            
        }
        
        for(int i = 0; i < arr.length; ++i) {
            if(arr[i] != 0) {
                sum += arr[i];
            }
        }
        
        return sum;
    }
    
    public static String run() {    
        return Long.toString(sieve());
    }
 
}

<C>

#include <stdio.h>
 
#define LIMIT 2000000
 
int run();
int isPrime(int num);
 
int main()
{
    return run();
}
 
int run()
{
    long long sum = 2;
    int i;
 
    for (i = 3; i <= LIMIT; ++i)
    {
        if (isPrime(i)) { sum += i; }
    }
 
    printf("Sum: %lld\n", sum);
 
    return 0;
}
 
int isPrime(int num)
{
    int i;
 
    if (num <= 1) { return 0; }
    else if (num == 2) { return 1; }
    else
    {
        if (num % 2 == 0) { return 0; }
        else
        {
            for (i = 3; i*i <= num; i += 2)
            {
                if (num % i == 0) { return 0; }
            }
 
            return 1;
        }
    }
}

<C: Eratosthenes`s sieve>

C는 배열 크기가 너무 크면 정상적인 실행이 안 됨.

<Java: Eratosthenes`s sieve>

public class Problem010 {
    private static final int LIMIT = 2000000;
    
    public static void main(String[] args) {
        System.out.println(new Problem010().run());
    }
    
    public String run() {
        boolean[] isNotPrime = new boolean[LIMIT];
        int lim = (int) Math.sqrt((double) LIMIT);
        long sum = 0;
        
        for(int i = 2; i < lim; i++) {
            if(isNotPrime[i] == false) {
                for(int j = 2*i; j < LIMIT; j += i) {
                    isNotPrime[j] = true;
                }
            }
        }
        
        for(int i = 0; i < LIMIT; i++) {
            if(!isNotPrime[i]) {
                sum += i;
            }
        }
        
        return Long.toString(sum);
    }
 
}

정답: 142913828923

실행시간은 30ms = 0.03초.

그냥 에라토스테네스의 체로 하자.