[백준 1929번] 소수 구하기

http://www.acmicpc.net/problem/1929

1929번: 소수 구하기

풀이) 

소수의 정의를 이용해서 풀어보았다. 사실 n / 2가 아닌 루트n으로 하면 더 최적의 알고리즘이 되지만, sqrt를 구현하지않았고, 대신 100만의 제한에 맞춰서 100만루트인 1000을 최대값으로 설정해두었다. 

#include <iostream>
using namespace std;

int is_prime(int n)
{
    int i;

    if (n < 2)
        return (0);
    i = 2;
    while (i <= n / 2 && i <= 1000)
        if (n % i++ == 0)
            return (0);
    return (1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int M, N;
	
    cin >> M >> N;
    for (int i = M; i <= N; i++)
        if (is_prime(i))
            cout << i << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!