소수 더하기 O(n) 최적화

1에서 100까지의 소수(decimal) 전부를 더하는 프로그램.

소수 찾기에서는 중복되는 횟수가 많아 root를 사용함으로써 확인의 개수를 현저하게 줄일 수 있다.

이중 루프에서도 n이 1000000개라고 하더라도 2번째 루프에서는 root로 1000개만을 탐색하므로 n의 1%만을 더해진다.

그러므로 이 소수 알고리즘은 O(n)과 가깝게 모든 소수를 찾아 더할 수 있다.

루트를 사용하는 것이 효과적인 까닭은 루트를 경계 위에 나오는 숫자들은 루트의 아래의 숫자의 배수 경우로 포함되는 이유다.

#include<stdio.h>
#include<math.h>
int main(){
 int sum = 0;
 for (int i = 2; i <= 100; i++){
  int prime = true;
  for (int j = 2; j <= sqrt((double)i); j++){
   if (i%j == 0){
    prime = false;
   }
  }
  if (prime)
   sum += i;
 }
 printf("%d\n", sum);
}