자바를 이용한 암호학 - 에라토스테네스의 체를 이용한 소수 찾기 과제

예전에 어디선가 소수과련된 문제를 풀었던 코드입니다.  

당시에 에라토스테네스의 체로 풀었습니다.

언어는 자바는 아니고 파이썬으로 했기때문에 알아서 보기 바람니다.. (자바나 파이썬이나.. 코드는 비슷 비슷하니..)

Q. 1부터 200백만 까지 소수의 합

원리..

[2, 3, 4, 5, 6, 7, ...]

1. 구하려는 숫자까지 모두 배열에 입력.

2. list[0] 부터 있는 숫자를 자기자신은 놔두고 그 후에 나오는 배수는 삭제

3. 2를 반복해 list배열의 마지막 숫자까지 확인한다.

예

초기      / [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ...]

list[0]=2 / [2, 3, 5, 7, 9, 11, ...]

list[1]=3 / [2, 3, 5, 7, 11, 13, 15, 17, 19, 23...]

list[2]=5 / [2, 3, 5, 7, 11, 13, 17, 19, 23...]

list[3]=7 / [2, 3, 5, 7, 11, 13, 17, 19, 23...]

list[4]=11 / [2, 3, 5, 7, 11, 13, 17, 19, 23...]

code

-----------------------------------------------------------

list = [2]        ## 배열의 초기 '2' 초기화..

max = 2000001     ## 200백만 까지 숫자..

for a in range(3, max):     ## 2는 있기 때문에 3부터 홀수만 배열에 입력한다.

if (a%2 == 0 ):     ## 짝수이면 건너 뜀

continue

list.append(a)      ## 홀수면 list배열에 추가..

print "list append end~"

for a in list:        ## list의 숫자를 a에 반복값으로 넣음..

cnt = 0       ## 자신을 제외한 숫자를 지워야하기 때문에 cnt변수 둠

b = 0

while (b < len(list)):       ## list 배열에 개수만큼만 반복

if (list[b]%a == 0):  ## 특정배열이 a로 나누어 떨어지면 배수로 반정

if(cnt != 0):   ## 그 숫자가 처음이 아니라면 삭제한다

list.remove(list[b])

if(cnt ==0):    ## but.. 그 숫자가 처음이라면 놔둔다.

cnt = cnt + 1

b = b+1

sum = 0

for a in list:

sum = sum + a

print "sum = ", sum

------------------------------------------------------------

결과값

sum = 직접 해보시기를...(대략적인 답은 약 천4백억 쯤 나올겁니다.)

!주의!

이 코드를 직접 똑같이 써도 실행은 되지만 약 하루정도 시간이 걸립니다.

이유는 매우 큰 숫자와 함께 이중반복문을 사용하였기때문입니다.

머 c나 c++에서는 이정도는 별것 아닌것도지만.. 파이썬은 반복문에 매우 느립니다.

그래서 이 문제에 대한 답을 얻으시려면 c나 c++로 수정후에 해보시길 권장합니다.

---

http://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

http://en.wikipedia.org/wiki/Sieve_of_eratosthenes