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,"는 소수아님"
#-*- 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부터 특정 양의 정수 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
댓글
댓글 쓰기