[BaekJoon] 백준 1978번 _소수찾기 for Java

 

 

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

1978번: 소수 찾기

 

 

 

 

 

 

 

---

 

 

 

소수찾기

 

 

https://ticssfm.tistory.com/19?category=1008893 

[Algorithm][Java] 소수를 나열하는 알고리즘, 소수인지 판단하기

 

 

전에 한번 정리한적이 있었던 문제였다.

 

 

 

 

 

소수임을 판단하는 방법에는 3가지가 있다. 

 

 

1. 짝수는 소수가 무조건 x -> 홀수랑만 비교하면 된다

2. 소수는 소수끼리 나누어지지 x

3. 판단하려는값의 루트값보다 작은 값만 확인하면 된다.

 

 

 

 

 

이 3가지를 모두 사용하려고 했는데.... 뭔가 잘 안돼서 결국 사용한 방법은 1번만 사용하였다.

 

 

 

 

내가 푼 코드

 

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


public class Baek1978 { // 소수 찾기
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		int count = 0;
		ArrayList<Integer> prime = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < N; i++) {	
			prime.add(i, Integer.parseInt(st.nextToken()));
		}
		
		for(int i = 0; i < N; i++) {
			if((prime.get(i) % 2) == 0) { // 짝수이면
				continue;
			} else { // 홀수임
				if(prime.get(i) == 1) {}
				else {
					for(int j = 3; j < prime.get(i); j += 2) {
						if(prime.get(i) % j == 0)break; // 나누어떨어지면 소수 x
						else {
							if((j+2) == prime.get(i)) count++;
						}
					}
					
				}

			}
			
		}
		
		if(prime.contains(2) == true) count++;
		if(prime.contains(3) == true) count++;
		System.out.println(count);
	}
}

 

 

 

 

내가 푼 방법은

 

1. 짝수인지 확인하고 홀수만 사용

2. 홀수이면 자기보다 작은 홀수와 나누어떨어지는지 일일히 확인!

 

 

 

 

비효율적인 코드를 사용하였다.

 

 

 

 

 

 

 

런타임에러때문에 오래걸렸다,,,,,,;;;

 

 

 

 

 

 

 

다른 사람 코드를 보고 익혀야지!!