[BOJ] 1929번: 소수 구하기 (C, C++, Java, Python3)

 

1929번: 소수 구하기

 

 

문제

---

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 

입력

---

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

 

출력

---

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

힌트

---

입력 범위를 보면 M이 1, N이 1,000,000일 때 최악의 경우가 됨을 알 수 있다.

 

만약 숫자 A를 소수인지 아닌지 판별할 때 1부터 A까지 반복하면서 나누어 떨어지는지 확인한다면 숫자가 커질수록 반복하는 횟수가 많아질 것이다.

조금 더 효율적으로 구현하고자 아래와 같은 방법을 사용할 수 있을 것이다.

• A / 2까지 반복한다.
• 1과 자기 자신이 아닌 다른 수로 나누어 떨어질 때 break를 걸어준다.
• 나누는 수를 2와 홀수들로 제한한다.

이것저것 줄인다면 시간초과는 면할지 모르겠으나 범위가 백만을 넘어서 천만까지 간다면 이조차도 통과를 장담하지 못한다.

 

아래 링크에서 소수를 판별하는 알고리즘인 에라토스테네스의 체를 공부하고 다시 풀어보자

 

풀이

---

에라토스테네스의 체를 사용하면 쉽게 풀 수 있는 문제이다.

실행 시간을 줄일 수 있는 여러 가지 방법들이 있으니 계속해서 시간을 줄여보는 것도 좋다.

 

C

#include <stdio.h>

int main(){
    int M, N, is_prime[1000001];

    scanf("%d %d", &M, &N);

    for(int i = 0; i < N + 1; i++)
    {
        is_prime[i] = 1;
    }

    is_prime[1] = 0;

    for(int i = 2; i < N + 1; i++)
    {
        for(int j = i * 2; j < N + 1; j+=i)
        {
            is_prime[j] = 0;
        }
    }

    for(int i = M; i <= N; i++)
    {
        if(is_prime[i] == 1)
        {
            printf("%d\n", i);
        }
    }

    return 0;
}

 

C++

#include <iostream>
using namespace std;

int main(){
    int M, N;
    int is_prime[1000001];

    cin >> M >> N;
    
    for(int i = 0; i < N + 1; i++){
    	is_prime[i] = 1;
    }

    is_prime[1] = 0;

    for(int i = 2; i < N + 1; i++)
    {
        for(int j = i * 2; j < N + 1; j+=i)
        {
            is_prime[j] = 0;
        }
    }

    for(int i = M; i <= N; i++)
    {
        if(is_prime[i] == 1)
        {
            cout << i << "\n";
        }
    }

    return 0;
}

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt(), N = sc.nextInt();
        int []is_prime = new int[N + 1];

        Arrays.fill(is_prime, 1);

        is_prime[1] = 0;

        for(int i = 2; i < N + 1; i ++)
        {
            for(int j = i * 2; j < N + 1; j+=i)
            {
                is_prime[j] = 0;
            }
        }

        for(int i = M; i <= N; i++)
        {
            if(is_prime[i] == 1)
            {
                System.out.println(i);
            }
        }

        sc.close();
    }
}

 

Python3

M, N = map(int, input().split())
is_prime = [1] * (N + 1)

is_prime[1] = 0

for i in range(2, N + 1):
    for j in range(i * 2, N + 1, i):
        is_prime[j] = 0

for i in range(M, N + 1):
    if is_prime[i]:
        print(i)