[JAVA] 백준 1978번 : 소수찾기

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

1978번: 소수 찾기

알고리즘 책에서 공부한 내용이라 두가지 방법으로 풀 수 있다고 생각함.

1. 소수 배열을 만들어서 입력한 수랑 비교
2. 입력받은 수를 하나하나 소수인지 판단

고민하다가, 배운거 좀 복습좀 하려고 1번으로 했음

import java.util.*;
import java.util.stream.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int[] isPrime = new int[N]; //소수인지 판별하고 싶은 배열
		int[] primeArr = new int[500]; //소수를 모아둔 배열
		int cnt = 0;
		
		for (int i = 0; i<N; i++) {
			isPrime[i] = sc.nextInt();
		}
		
		int ptr = 0; //primeArr에 소수 추가할 때마다 증가시킬 변수
		primeArr[ptr++] = 2; //소수에 2추가
		primeArr[ptr++] = 3; //소수에 3추가
		
		for (int n = 5; n <=1000; n += 2) { //5부터 1000까지 연산 + 홀수만 고려
			boolean flag = false;
            //정사각형 기준 생각
			for (int i = 1; primeArr[i] * primeArr[i] <= n; i++) {
				if (n % primeArr[i] == 0) { //나눠떨어지면 소수가 아님
					flag = true;
					break;
				}
			}
			if(!flag) {
				primeArr[ptr++] = n;
				
			}
		}
		
		for (int a = 0; a < isPrime.length; a++) {
			int n = isPrime[a];
			if(IntStream.of(primeArr).anyMatch(x -> x == n)) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
		
		
		
	}

}

여기서

for (int i = 1; primeArr[i] * primeArr[i] <= n; i++)

이 놈은

10 * 10

= 1 * 100 = 2 * 50 = 4 * 25 = 5 * 20

= 100 * 1 = 50 * 2 = 25 * 4 = 20 * 5

라고 표현할 수 있으니까, 굳이 보라색이랑 초록색 모두 고려할 필요없이 한 세트만 조사해주면 된다.

그걸 표현해주기 위한 반복문임

이렇게 하면 시간을 단축할 수 있다.

여튼튼 소수 배열에 이미 있는 소수와 나눠떨어지면, 소수가 아니고

끝까지 반복문을 돌았는데 나눠떨어지는 경우가 없으면 소수배열에 추가한다.

 

if(IntStream.of(primeArr).anyMatch(x -> x == n))

이 놈은 소수배열에 내가 조사하고 싶은 배열에 소수가 몇개있는지를 조사하는 라인이다.

그냥 isPrime[i]으로 썼는데, 그냥 컴파일에러가났다. 에러 내용보니까 로컬어쩌구 뭐시라뭐시라 그랬는데 그냥 귀찮아서 조건문 위에다 정수 변수 하나 뚫어서 받았다.

 

근데 이렇게 풀고 난 후에, 코드가 좀 너무 길기도하고, 쓸데없는 부분까지 구현한거 같다는 생각이 들어서 2번 방법으로도 한번 짜보고싶어졌다. 하지만 아쉽게도 귀찮아서 짜지않았다.

사실 한번 시도해봤는데, 잘 안되길래 말았음ㅠ