[백준]_1929번 : 소수 구하기(파이썬 and C언어)

1929번: 소수 구하기

전략

여느 때와 다름없이 검사할 범위가 큰 소수 문제는 에라토스테네스의 체를 사용하는 문제이다. 시간 초과가 안 나오게 조심해야 하는 문제들 중 하나이기 때문에 시간복잡도를 최소화시키면서 코딩을 해야 한다. 

 

시도 1(Python)

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

for i in range(m,n+1):
    if i==1:
        continue
    for j in range(2,int(i**0.5)+1):
        if i%j==0: 
            break   
    else:
        print(i)

<평가>  왠지 모르게 느리다(5224 ms). 아래와 같은 수정을 거치면 조금 더 빨라지지 않을까?

수정

import sys
input = sys.stdin.readline
tail, head = map(int, input().split())

def ifprime(n):
    if n == 1:
        return 0
    for i in range(2, int(n ** 0.5) + 1):
        if not n % i: return 0
    return 1

for num in range(tail, head + 1):
    if ifprime(num): print(num)

3072 ms 까지 줄였다!

시도 2(C언어)

#include <stdio.h>
#include <math.h>
int ifprime(int n){
    if(n==1) return 0;
    for(int i=2;i<int(sqrt(n))+1;i++){
        if(n%i==0) return 0;
    }	
    return 1;
}
int main() {
    int tail, head;
    scanf("%d %d",&tail, &head);
    for(int num=tail;num<head+1;num++){
        if(ifprime(num)) printf("%d\n",num);
    }	
    return 0;
}