소수

### 소수(Prime) ###

: 1보다 크고 약수가 1과 자기자신인 수

​

 

 

< 소수 찾는 방법>

 

1. 반복문 이용

def prime(x):
	#1을 제외하므로 2부터 시작
    for i in range(2,x):
		
		#나눠지는지 파악 
        if x % i == 0: 
            return False 
        
		#시간 복잡도가 x**0.5이기 때문에 
        if i * i > x:
            break 
    
	return True 

 

 

 

 

2. ★에라토스테네스의 체★

: 어떤 수를 기준으로 해당 수의 배수를 다 지워가며 소수 찾기

def era_prime(x):
	a = [0 for _ in range(x+1)] #a: 소수인 경우 0나타낸다. 
	p = []  #p: 소수값 저장 list
	
	for i in range(2, x):
		#소수인 경우
		if a[i] == 0:
			p.append(i)
		
		#소수가 아닌 경우
		else:
			continue
		
		#i의 배수 값들 1로 바꿔주기
		for j in range(i **2, x, i):
			a[j] = 1
            
	return p