[구현] (2-8) N까지의 소수 구하기 vs 한 숫자의 소수여부 판별

문제:  뒤집은 소수

 

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력 한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.
뒤집는 함수인 def reverse(x) 와 소수인지를 확인하는 함수 def isPrime(x)를 반드시 작성하 여 프로그래밍 한다.

<입력설명>
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.

<출력설명>
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

입력예제
5
32 55 62 3700 250

출력예제

23 73

 

https://leerosepark.tistory.com/31

[구현] (2-7) 소수찾는 가장 작은 시간복잡도 : 에라토스테네스의 체

이전글이 N까지의 소수를 구하는 문제였다면,

위 문제는 N이 소수인지 아닌지를 구하는 문제이다.

 

이는 약수를 구하는 방법을 응용하면 되는 방법이다.

https://leerosepark.tistory.com/25 

 

'N이 소수이다' 라는 말은 'N이 (1, N)외의 약수가 있다' 라는 말. 이를 위 링크의 내용을 응용하면,

'N이 2~sqrt(N)까지 중 약수가 없다' 가 된다.

즉 한 숫자의 소수여부 판별의 시간복잡도는 O(sqrt(N))

 

import sys
input = sys.stdin.readline
from math import sqrt
from math import pow
from collections import deque

N = int(input())
num_list = list(map(int, input().split()))
prime_list = []

def ifPrime(x: int):
    if x== 1 or x==2:
        return True
    median = int(sqrt(x))
    for i in range(2, median+1):
        if x%i == 0:
            return False
    return True

def reverse(x: int):
    digit_list = deque()
    while x != 0:
        digit_list.appendleft(x % 10)
        x = int(x/10)
    new_x = 0
    # print(digit_list)
    for digit, num in enumerate(digit_list):
        new_x += int(pow(10, digit)) * num
    return new_x

for i in range(N):
    num_reversed = reverse(num_list[i])
    # print(num_reversed)
    if ifPrime(num_reversed):
        print(num_reversed, end=" ")

 

print(num_reversed, end=" ")

 

print시에 end= 을 이용하는 방법도 외우두자