Prime Numbers 소수 [Python]

HyunMin Yang·2022년 8월 6일

Prime python

Algorithm

목록 보기

1/4

소수 (Prime Number)

약수가 1과 자신뿐인 수

예제)
첫번째 수 = 6
약수 = 1,2,3,6
답 = 소수 아님

두번째 수 = 3
약수 = 1,3
답 = 소수

소수찾기

약수 찾기와 비슷하지만, 나누어지는게 있으면 소수가 아님
1과 N은 당연히 나눠지므로 범위는 2부터 N까지 해야한다

N = int(input())

for i in range(2,N):
  if N%i ==0:
    print("소수가 아님")
    break

위 코드는 입력된 수가 소수인지 아닌지를 판단해주는 코드이다. N이 2부터 N까지 돌면서 i가 되고 i가 N으로 나누어 떨어지는지 확인한다. 만약 나누어 떠러지면 소수가 아니고 나누어 떠러지지 않으면 소수이다.

함수로 찾는 방법 또한 있다

def is_prime(n):
  for i in range(2, n):
    if n % i == 0:
      return False
      break
  #return True
  else:
    return True

print(is_prime(17))

is_prime(n)에 입력된 숫자가 소수면 True, 소수가 아니면 False를 출력한다.

범위 내에서 소수찾기

N보다 작은 소수찾기

N = int(input())
prime_number = []

for i in range(2,N):
  if is_prime(i):
    prime_number.append(i)
print(prime_number)

이 코드는 for문이 N까지 돌면서 소수들을 list에 넣어 N까지의 모든 소수를 찾아준다.

M보다 크고 N보단 작은 소수찾기

M = int(input())
N = int(input())
prime_number = []

for i in range(M,N):
  if is_prime(i):
    prime_number.append(i)
print(prime_number)

range 범위를 M부터 N으로만 바꾸면 됨

에라토스테네스의 체

설명:

빈 리스트를 만들어 숫자의 인덱스와 숫자가 같다고 가정한다.
소수로 판면되면 True이고 아니면 False로 바꾼다.
마지막에 True인 친구들의 인덱스만 뽑아낸다.
방법:

N+1 개의 True가 담긴 리스트를 만든다
0과 1은 Flase로 만든다.
리스트를 처음부터 끝까지 반복하는데,
그 다음부터 True인 수를 만나면 그 수 외 배수들을 전부 False로 바꾼다.

def prime_list(n):
  sieve = [True]*(n+1)
  for i in range(2,int(n**(1/2))+1):
    if sieve[i] == True:
      for j in range(i*2, n, i):
        sieve[j] = False

  prime_number = []
  for i in range(2,n):
    if sieve[i]:
      prime_number.append(i)
  return prime_number

print(prime_list(100))