백준 1978번 소수 찾기 문제 해답

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

기본적인 소수찾기 문제이다

소수찾기의 알고리즘은 기본적으로 에라토스테네스의 체를 많이 이용한다

에라토스테네스의 체를 처음 들어보셨으면 아래의 글에 들어가 ppt를 읽고오면 도움이 될 것이다.

 

 

2020/02/28 - [알고리즘] - [소수 찾기]에라토스테네스의 체

[소수 찾기]에라토스테네스의 체

 

 

 

 

다음은 c언어 코드이다

#pragma warning (disable:4996)				//M~N까지 1978번 소수 찾기 (c)
#include <stdio.h>
#define true 0			//소수
#define false 1		//소수가 아닌수
#define MAX 1000000
int isPrime[MAX];
int main()
{
	int M, N;
	isPrime[0] = isPrime[1] = false;			//0과 1은 소수가 아니다
	scanf("%d %d", &M, &N);
	for (int i = 2; i < MAX; i++)				//2부터 시작해서 특정한 숫자의 배수들은 소수가 아니다
	{
		if (isPrime[i] == false) continue;		//이미 소수가 아닌 걸로 판정된 숫자들은 그냥 지나가고
		for (int j = i + i; j < MAX; j += i) {		//판정되지 않았다면 그의 배수들을 소수가 아닌 숫자로 판정한다
			isPrime[j] = false;
		}
	}
	
	for (int i = M; i < N + 1; i++) {			//판정되지 않은 숫자들(소수들)을 모두 출력한다
		if (isPrime[i] == true) printf("%d\n", i);
	}
	return 0;
}

 

정적 배열을 생성할 때 모든 배열요소가 0으로 초기화되기 때문에 true를 0로 주었다는 것을 주의합시다.

일단 모든 수를 소수로 생각하고 그 중에서 소수가 아닌 것들을 1로 초기화한다는 방식입니다.

true를 1로 주고 싶다면 isPrime이 아닌 isNotPrime으로 바꿔주면 이해가 쉬울 것이다

다음 c++과 자바도 동작원리는 비슷하기에 설명은 생략한다.

 

 

 

 

다음은 c++코드이다

#include<iostream>				//M~N까지 1978번 소수 찾기  (c++)
using namespace std;
const int MAX = 1000000;
bool c[MAX + 1];
int main()
{

	c[0] = c[1] = true;				//0과 1은 소수가 아니다
	for (int i = 2; i * i <= MAX; i++)		//2부터 시작해서 특정한 숫자의 배수들은 소수가 아니다
	{								//이미 소수가 아닌 걸로 판정된 숫자들은 그냥 지나가고
		if (c[i] == false)					//판정되지 않았다면 그의 배수들을 소수가 아닌 숫자로 판정한다
		{
			for (int j = i * i; j <= MAX; j = j + i) \	
				c[j] = true;				
		}
	}
	int m, n;
	cin >> m >> n;

	for (int i = m; i <= n; i++)
	{
		if (c[i] == false)
			cout << i << '\n';		//판정되지 않은 숫자들(소수들)을 모두 출력한다
	}
	return 0;
}

 

 

 

 

다음은 자바 코드이다

import java.util.Scanner;
public class Main {
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		final int max = 1000004;
		boolean number[] = new boolean[max];
		int M = scan.nextInt();
		int N = scan.nextInt();
		for(int i = 0;i<max;i++){
			number[i] = true;
		}
		number[0] = number[1] = false;				//0과 1은 소수가 아니다
		for(int  i =2; i< max;i++)				//2부터 시작해서 특정한 숫자의 배수들은 소수가 아니다
		{
			if(number[i] == false) continue;		//이미 소수가 아닌 걸로 판정된 숫자들은 그냥 지나가고
			for(int j = i+i; j<max; j+=i) {		//판정되지 않았다면 그의 배수들을 소수가 아닌 숫자로 판정한다
				number[j] = false;
			}
		}
		
		for(int i = M; i<=N; i++){				//판정되지 않은 숫자들(소수들)을 모두 출력한다
			if(number[i] == true) System.out.println(i);
		}
	}
}