소수
소수를 찾는 함수 구현 (기본)
def isPrime(a):
for i in range(2,a):
if n%i==0:
return False
return True
약수의 특성을 활용해서 연산 횟수를 반으로 줄일 수 있다.
약수의 특성
따라서, 우리는 기존 for문이 2에서 a-1까지 반복했던 것을 2에서 a의 제곱근까지만 돌도록 처리해주어 연산 횟수를 절반에 가깝게 줄여줄 수 있다.
연산 횟수를 반으로 줄이는 코드
import math
def isPrime(a):
for i in range(2,int(math.sqrt(a))+1): #a의 제곱근을 정수화 한 후 +1
if n%i == 0:
return False
return True
여러 개의 수에 대하여 소수 판별을 해주어야 하는 상황이라면 어떨까. 100 ~ 300 사이의 모든 소수를 구해야하는 상황이라면 우리는 위의 방식을 이용해 하나하나 모든 수를 판별해줘야할까?
에라토스테네스의 체 방식이란?
에라토스테네스의 체 방식으로 코드 구현
def isPrime(n):
arr=[True]*(n+1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
arr[0]=False # 인덱스 0은 단순히 인덱스와 특정 수의 값을 맞춰주기 위함
arr[1]=False # 소수는 2부터 시작
for i in range(2,n+1):
if arr[i] == True :
j=2
while (i*j) <=n:
arr[i*j]=False
j+=1
return arr
arr = isPrime(50) # 0~50 사이의 소수 배열을 구하기 위한 함수
for i in range(len(arr)):
if(arr[i]==True:
print(i,end=' ')
import math
def isPrime(n):
arr=[True]*(n+1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
arr[0]=False # 인덱스 0은 단순히 인덱스와 특정 수의 값을 맞춰주기 위함
arr[1]=False # 소수는 2부터 시작
for i in range(2,int(math.sqrt(n))+1): # 이 부분만 바뀜
if arr[i] == True :
j=2
while (i*j) <=n:
arr[i*j]=False
j+=1
return arr
arr = isPrime(50) # 0~50 사이의 소수 배열을 구하기 위한 함수
for i in range(len(arr)):
if(arr[i]==True:
print(i,end=' ')