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...