★[python_파이썬_pass_소수관련 알고리즘 종합 복습]백준_1929번_소수 구하기_풀이

공부하는허딩크 : https://www.youtube.com/live/KtmItpIeYu4?feature=shared

 

일단 에라토스테네스의 체 알고리즘을 활용해서 풀어보았다.

잠깐 생각이 안나서 복습하고 옴.

에라토스테네스의체 알고리즘 : https://heodinkcodingdiary.tistory.com/64

[python_파이썬_pass_에라토스테네스의체 알고리즘]백준_4134번_다음 소수_풀이

 

<첫번째 시도 : 맞았습니다 _에라토스테네스의 체 알고리즘. 268ms>

소수판별 알고리즘으로도 풀 수 있었던 문제이지만, 에라토스테네스의체 알고리즘을 훈련하기 위해서사용했다.

import sys

input = sys.stdin.readline

#에라토스테네스의체 알고리즘 사용

M, N = map(int, input().split())

graph = [1] * (N + 1)

graph[0] = graph[1] = 0

p = 2

while (p * p) <= N:

    if graph[p]:

        for i in range(p * p, N + 1, p):

            graph[i] = 0

    p += 1

for i in range(M, N + 1):

    if graph[i]:

        print(i)

 

★ 계속 헷갈리는게 에라토스테네스의체 알고리즘과 소수판별 알고리즘이다.

소수판별알고리즘에서는 p = 5를 주어 while은 동일하게 돌리고, 바로 if 정수 % 5 == 0 또는 정수 % (5 + 2) == 0이면 ㄱㄷreturn 0을 주어 소수가 아닌 것으로 판별한다. 그 다음 5 += 6을 해서 반복한다.

1. 에라토스테네스의체 알고리즘

 1) 위에 코드와 같이 처음에는 모든 수를 소수라고 가정해서 리스트를 만든다.

 2) 0과 1은 무조건 소수가 아니기 때문에 0 또는 False를 넣어준다.

 3) 인덱스 2부터 동작할건데. while에 왜 p * p의 조건이 오는가? => N이 2 또는 3일 때 는 해당 숫자는 소수기때문에 확인 할 필요 없다.

 4) N이 4라면 일단 graph[2] = 1이 참이라서 for문이 돌고, 4부터, 6, 8, 10...2를 제외한 2의 배수들을 뽑아내어 graph[i]에다가 주면 해당 인덱스들은 소수가 아니라고 체크된다.

 5) 2와 동일하게 3을 제외한 3의 배수들은 소수가 아니라고 체크할 수 있다. p가 4, 6등의 숫자가 오면 어차피 이전에 다 변경되어 있다.

 6) p = 5일때 25 <= 26일 경우 5를 제외한 5의 배수들은 모두 소수가 아닌 걸로 체크된다.

 7) 즉 해당 알고리즘은 graph의 엔덱스에 소수가 아닌 수들은 0으로 소수들은 1로 처리가 되어 있으므로 어떤 구간의 소수들을 불러오는데 적합하다.

 

<두번째 시도 : 맞았습니다._소수판별 알고리즘 사용 1492ms>

어떤 하나의 정수를 매번 소수인지 판별해서 출력하게 만들었다.

import sys

input = sys.stdin.readline

#소수판별알고리즘 사용

M, N = map(int, input().split())

def Prime(n):

    if n <= 1:

        return 0

    if n <= 3:

        return 1

    if n % 2 == 0 or n % 3 == 0:

        return 0

   

    p = 5

    while (p * p) <= n:

        if n % p == 0 or n % (p + 2) == 0:

            return 0

        p += 6

    return 1

for i in range(M, N + 1):

    if Prime(i):

        print(i)

 

<세번째 시도 : 시간초과>

제곱근 미사용

import sys

input = sys.stdin.readline

def Prime(n):

    if n <= 1:

        return 0

    elif n <= 3:

        return 1

   

    for i in range(2, n):

        if n % i == 0:

            return 0    

    return 1

#소수판별알고리즘 사용

M, N = map(int, input().split())

for i in range(M, N + 1):

    if Prime(i):

        print(i)

 

<네번째 시도 : 맞았습니다. 소수판별 알고리즘_제일 느림 3276ms > 

import sys

input = sys.stdin.readline

def Prime(n):

    if n <= 1:

        return 0

    elif n <= 3:

        return 1

   

    for i in range(2, int(n**0.5) + 1):

        if n % i == 0:

            return 0    

    return 1

#소수판별알고리즘 사용

M, N = map(int, input().split())

for i in range(M, N + 1):

    if Prime(i):

        print(i)

 

<다른사람 풀이 참고>

에라토스테네스의체 알고리즘을 활용한것 같은데....나는 배열을 사용했고, 아래의 코드는 리스트를 사용해서 좀 더 메모리를 절약할 수 있다.

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

A = [i for i in range(m+1)]

for i in range(2, m+1):

    if A[i] != 0:

        for j in range(2*i, m+1, i):

            if A[j] == j: A[j] = 0

for i in range(max(2, n), m+1):

    if A[i] == i: print(A[i])

와... 알고리즘을 활용해서 문제에 맞게 변형한 것 같은데 이해하기 쉽지 않네....

 

<코드 응용>

왜 이제까지 이걸 몰랐지? else가 if 뿐만아니라 for와 while에서 쓸 수 있는걸??

 

1) 속도가 느린 소수판별 알고리즘 응용_5332ms

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

for i in range(n, m + 1):

    if i <= 1:

        continue

    elif i <= 3:

        print(i)

    else:

        for j in range(2, int(i**0.5) + 1):

            if i % j == 0:

                break

        else:

            print(i)

 

2) 소수판별 알고리즘 응용_이건 시간초과

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

for i in range(n, m + 1):

    if i <= 1:

        continue

    if i <= 3:

        print(i)

    if i % 2 == 0 or i % 3 == 0:

        continue

   

    p = 5

    while (p * p) <= i:

        if i % p == 0 or i % (p + 2) == 0:

            continue

        p += 6

    else:

        print(i)

 

while문 안에 continue대신 break로 변경  2560ms

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

for i in range(n, m + 1):

    if i <= 1:

        continue

    if i <= 3:

        print(i)

    if i % 2 == 0 or i % 3 == 0:

        continue

   

    p = 5

    while (p * p) <= i:

        if i % p == 0 or i % (p + 2) == 0:

            break

        p += 6

    else:

        print(i)

 

3)에라토스테네스의체 알고리즘 활용 516ms

max(2, n)을 사용해서 n이 2보다 작을 경우 대비해야함

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

graph = [i for i in range(m + 1)]

for i in range(2, m + 1):

    if graph[i] != 0:

        for j in range(i * 2, m + 1, i):

            graph[j] = 0

for i in range(max(2, n), m + 1):

    if graph[i]:

        print(i)