백준 1929번 파이썬

내가 생각한 구조는

M~N을 돌면서 소수 검사를 하고 만약 나누어 떨어지면(소수가 아니면) 플래그 변수 1로 바꾸고 바로 빠져나옴 --> flag변수 0일때만 출력시킴 이다

#!usr/bin/python3

#M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
#[입력]
#첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. 
#(1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
#[출력]
#한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
M, N = map(int, input().split())
#flag변수 사용함
for n in range(M, N):
    prime = 0
    for i in range(2, n):  
        if n % i == 0:
            prime = 1
            break 
    if prime == 0:
        print(n)

이렇게 적었더니 시간 초과가 떴다

찾아보니 n-1까지 반복문을 돌릴게 아니라 루트n까지만 돌리는거였다

게다가 (M, N+1)인데 범위도 틀렸다

ㄴ아직 파이썬이 익숙치 않다-끝문자 포함 안되는 것임!

import math

M, N = map(int, input().split())
#flag변수 사용함
for n in range(M, N+1):
    prime = 0
    for i in range(2, math.ceil(math.sqrt(n)): 
        if n % i == 0:
            prime = 1
            break  
    if prime == 0:
        print(n)

암튼 루트n으로 고치는데

float라 안되고 올림을 시켜주면 3이 문제다
for문이 2부터 시작인데 루트3을 올림하면 2이다
결국 range(2,2)가 되어 동작하지 않는다..

+제출시에는 출력초과가 뜬다

https://leejunggae.tistory.com/3
를 참고해 소수 아닌 수의 배수를 없애는 아이디어로 작성했으나

import math

M, N = map(int, input().split())
N+=1
prime = [True] * N
for n in range(M, N):
    for i in range(2, int(N**0.5)+1): 
        if prime[i]:
            for j in range(2*i, N, i):
                prime[j] = False
        
for i in range(M, N):
    if i > 1 and prime[i] == True:
        print(i)

3중 반복문이 되어 시간초과

import math

M, N = map(int, input().split())
def isPrime(m, n):
    n+=1 #함수를 삭제하면 이 줄이 오류 뜬다 입력받고 변화시키는건데 왜 오류가 나지?
    prime = [True] * n
    for i in range(2, int(n**0.5)+1): 
        if prime[i]:
            for j in range(2*i, n, i):
                prime[j] = False
            
    for i in range(m, n):
        if i > 1 and prime[i] == True:
            print(i)
isPrime(M, N)

^이렇게 수정하여 성공

<기억할 함수>
루트 변환 함수
math.sqrt()

소수 변환 함수
올림 math.ceil(n)
내림 math.floor(n)
반올림 round(n)