백준 알고리즘[파이썬] 1929번: 소수 구하기 ,1978번: 소수찾기

백준 알고리즘[파이썬] 1929번: 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 

3 16

예제 출력

3 5 7 11 13

소스코드

M,N=map(int,input().split())
*s,=range(N+1)

for i in s[2:]:
    if s[i]:
        s[2*i::i]=[0]*(N//i-1)
        if(i>=M):print(i)

M<= x <= N 사이에 있는 소수 x 를 구해야한다. 0~N까지의 수열을 만들 후 1보다 큰 값들의 배수를 제거한다.(0 할당)

초기값 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

* asterik 역할은 list literal:  https://www.python.org/dev/peps/pep-0448/

0을 할당하면 if s[i] 조건에 의해서 0 아닌 i값들만 실행 : 2,3,5,7,11,13

• 2의 배수  [0, 1, 2, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13]  # s[4::2] -> 4번쨰, 6번째, 8번째...
• 3 의 배수[0, 1, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13]   # s[6::3] ->,6번째, 12번쨰
• 5의 배수 [0, 1, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13]   # s[10::5] -> 10
• 7의 배수 [0, 1, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13]
• 11의 배수 [0, 1, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13]
• 13의 배수 [0, 1, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13]

입력한 range내에서 출력해야하므로 M보다 큰 소수만 출력

 

---

백준 알고리즘[파이썬] 1978번: 소수찾기

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 복사

4

1 3 5 7

예제 출력 

3

소스코드

input()
print(sum(all(i%j for j in range(2, i))*i>1 for i in map(int,input().split())))

입력받은 값들 중에서 1 보다 커야한다.

소수는 자기 자신과 1로만 약수로 갖는다. 1 보다 큰 입력값 중에서 각 값을 자기보다 작은 값으로 나누었을때 나머지가 0이 나오지 않아야 소수이다

파이썬을 comprehension을 이용해서 for loop과 조건문을 축약해서 표현한다. 하단에는 우리에게 익숙한 형태로 바꾼 것이다.

comprehension 중첩 형태 :  [출력 for value in iterables if 조건  for value in iterables if 조건]

• list comprehension    [키:값  for 키값 in iterables  if 조건]
• set comprehension   {키:값  for 키값 in iterables  if 조건}
• dictionary comprehension {키,값  for 키값 in iterables.items() if 조건}

all() 함수에는 iterable에 0 이 포함되면 False가 나온다. 이것을 이용해서 소수인 경우 True가 나오기 때문에 합을 구하면 갯수가 나온다.

for i in [1,3,5,7,8]:
    if i>1:
        print(list(i%j for j in range(2, i)))

[1]

[1, 2, 1]

[1, 1, 3, 2, 1]

[0, 2, 0, 3, 2, 1]

for i in [1,3,5,7,8]:
    if i>1:
        print(all(i%j for j in range(2, i)))

 

True

True

True

False

불리언값의 합을 구하면 True의 갯수가 나온다. 1 3 5 7 8 인 경우 소수는 3개