python2 prime number(소수) 구하는 알고리즘

소수 : 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수
두 가지 방법이 있다.


첫 번째, 2부터 특정 양의 정수 n까지로 n을 나누었을 때 약수가 자기 자신 n만 있는 경우이다. 예를 들어, 7을 2,3,4,5,6,7로 순서대로 나누어 본다. 그리고 자기 자신 7 이외에 약수가 존재 하지 않는다면 7은 소수가 된다.

#-*- coding: utf-8 -*-

i = input("숫자") # 숫자를 입력 받아서 i에 할당
j = 2

while(True): # 2부터 시작해서 i를 j로 나누어서 나머지가 0이 될 때까지 j를 계속 증가
    if(i%j ==0):
        break
    j +=1

if (i==j): # i와 j가 같을 때 즉 j가 i 자기 자신과 같으면 소수다.
    print i,j
    print i,"는 소수임"
else:
    print i,j
    print i,"는 소수아님"

숫자7

7 7

7 는 소수임

두 번째, 첫 번째 방법처럼 2부터 굳이 자기 자신까지 나누어 볼 필요 없다. 2부터 특정 양의 정수 n의 제곱근 까지로 n을 나누었을 때 약수가 존재 한다면, n은 소수가 아니다. 예를 들어, 양의 정수 25가 소수인지 확인하기 위해서는, 2부터 25의 제곱근인 5인 (2,3,4,5)로 25를 나누었을 때 약수가 존재 한다면 25는 소수가 아니다.

 #-*- coding: utf-8 -*-
import math

i = input("숫자") # 숫자를 입력받아서 i에 할당
j = 2

while(True):
    if(j<= math.sqrt(i)): # i가 25일 때, 2,3,4,5 까지 나누어봄
        if(i%j==0):
            print i,j
            print i,"는 소수아님"
            break
        else:
            j = j+1

    else: # 6~ 25 인 경우
        print i,j
        print i,"는 소수임"
        break

첫 번째 방법을 이용하여, 숫자를 입력 받아 2부터 입력받은 숫자까지의 소수의 합을 구해보기

#-*- coding: utf-8 -*-

i = input("숫자")

j=2

sum=0

for j in range(2,i+1):

    k=2

    while(True):

        if(j%k==0):

            break;

        k+=1

    if(j==k):

        sum+=j

        

print sum