[백준알고리즘/기본 수학 2단계] 1978번 문제 : 소수 찾기

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 1978번 문제 소수 찾기를 풀어봤습니다

소수가 뭔지만 알면 어렵지 않게 풀 수 있는 문제입니다

제가 푼 방법들에 대해서 알아보겠습니다

 

---

문제 링크입니다

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

1978번: 소수 찾기

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

 

---

 

 

문제 풀이

첫 번째 방법

기본적인 소수 판별 방법으로 풀은 방식입니다

2부터 하나씩 더해서 소수인지 판별하려는 수와 나누었을 때 나누어 떨어지면 소수가 아니게 됩니다

참고로 1은 소수가 아닙니다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 변수 및 StringTokenizer 변수 선언 및 데이터 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer.parseInt(br.readLine());		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int count = 0; // count변수
		
		while(st.hasMoreTokens()) // 반복문 시작
			if(isPrime(Integer.parseInt(st.nextToken()))) // 소수 판별 메서드 호출 -> count++
				count++;
		
		System.out.print(count); // 결과 출력
	}
	
	static boolean isPrime(int Number) // 소수 판별 메서드 선언
	{
		if(Number == 1) // 1은 소수x
			return false;
				
		for(int i = 2; i < Number; i++) // 2부터 나누어떨어지면 소수x
			if(Number % i == 0) return false;
		
		return true;
	}
}

 

---

 

두 번째 방법

위의 방식과 똑같지만 2부터 소수인지 판별하려는 수의 제곱근만큼 더한 값이 나누어 떨어지면 소수가 아니게 됩니다

예를 들면

만약 N이 12라 하면, 12의 제곱근은 3.46입니다

여기서 약수를 구하면 2 * 6, 3 * 4, 4 * 3, 6 * 2가 나옵니다

결국 4를 넘어가면 역으로 뒤집었을 때와 값이 같아지게 됩니다

그러므로 4 이상은 나누어봤자 의미가 없게 되는 것 입니다

제곱근을 사용하면 시간을 많이 단축할 수 있습니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 변수 및 StringTokenizer 변수 선언 및 데이터 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer.parseInt(br.readLine());		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int count = 0; // count변수
		
		while(st.hasMoreTokens()) // 반복문 시작
			if(isPrime(Integer.parseInt(st.nextToken()))) // 소수 판별 메서드 호출 -> count++
				count++;
		
		System.out.print(count); // 결과 출력
	}
	
	static boolean isPrime(int Number) // 소수 판별 메서드 선언
	{
		if(Number == 1) // 1은 소수x
			return false;
		
		for(int i = 2; i <= Math.sqrt(Number); i++) // 2부터 나누어떨어지면 소수x
			if(Number % i == 0) return false;
		
		return true;
	}
}

 

---

 

에라토스테네스의 체

소수의 배수들을 전부 지워나가는 방식으로 소수를 구하는 방법입니다

이 방법도 마찬가지로 구하려는 수의 제곱근까지만 배수를 곱해주면 됩니다

에라토스테네스의 체를 사용해 소수를 기록한 배열을 만든 후 비교하여 소수인지 아닌지 판별해줍니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main3 {
	public static void main(String[] args) throws IOException {
		// BufferedReader 변수 및 StringTokenizer 변수 선언 및 데이터 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Integer.parseInt(br.readLine());		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int count = 0; // count변수
		
		boolean[] Prime = new boolean[1001]; // 소수판별 배열 선언		
		Prime[0] = true;
		Prime[1] = true;
		
		// 에라토스테네스의 체 -> 제곱근까지만 반복한다 -> Prime배열이 true이면 소수x
		for(int i = 2; i <= Math.sqrt(1000); i++) {
			if(Prime[i] == true)
				continue;
			
			for(int j = i * i; j < 1001; j = j + i)
				Prime[j] = true;
		}
		
		while(st.hasMoreTokens()) // 반복문 시작
			if(Prime[Integer.parseInt(st.nextToken())] == false)
				count++;
		
		System.out.print(count);
	}
}

 

여기까지 세 가지 방법으로 풀어봤습니다

이제 속도를 비교해보겠습니다

 

---

 

속도 비교

1번 : 반복문 사용

2번 : 반복문(제곱근) 사용

3번 : 에라토스테네스의 체 사용

메모리는 3번 방식이 제일 빠르게 나왔습니다

속도는 역시 2번 방식이 제일 빠르게 나왔네요

 

2번 방식으로 풀은 것이 등수가 2등에 들어서 올려봅니다 :)

 

이상 백준 알고리즘 1978번 소수 찾기를 풀은 내용이었습니다

 

다음 문제 : 2021.06.20 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 2단계] 2581번 문제 : 소수