조띵의지극히개인적인공간

원문

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

Find the sum of all the primes below two million.

번역

10보다 작은 소수의 합은 2 + 3 + 5 + 7 = 17 이다.

2백만보다 작은 모든 소수의 합을 구하라.




내맘대로 해설 : 소수목록을 가지고 있고 각 숫자들별로 소수임을 판독하려 했으나...매우 느린 속도로 좌절하고...
배열 200만개 만들고 소수를 발견할때 마다 배열에 set을 해두어 검색하는 방식으로 했다 메모리는 많이 차지하게 되지만 속도만큼은 월등하다.
메모리가 염려되는 것을 대비하여 비트연산(--v)으로도 구현해보았으나 속도는 살짝 저하되었다...
아래에서 주석부분이 비트연산으로 계산하는 방식..


void func()

 char *DataList=NULL;
 int Sum=0;

 
 DataList = new char[2000000];
 memset(DataList, 0x00, 2000000);


 for (int i=3; i<2000000 ; i+=2)
 {
  //if (DataList[i/8] & (1<<(i%8))) continue;
  if (DataList[i]) continue;
 
  for (int n=0; n<2000000; n+=i)
  {
   //DataList[n/8] |= 1<<(n%8);
   DataList[n]=true;
  }

  Sum+=i;
 }
 printf("Value = %d\n", Sum);

 delete [] DataList;

}

저작자 표시
신고
Posted by 조띵


티스토리 툴바