[백준 1759] 소수의 연속합 - JAVA

(수정)

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

public class Main {

	static int n;
	static ArrayList<Integer> list = new ArrayList<Integer>();;
    static boolean prime[];
	public static void main(String[] args) throws Exception {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		n = Integer.parseInt(br.readLine());
		prime = new boolean[n + 1];

		primeNumber();
//		for(Integer i : list) {
//			System.out.println(i);
//		}
		System.out.println(countPrime(n));
	}
	public static void primeNumber() {
		for(int i = 2; i <= (n+1)/2; i++) {
			for(int j = 2; j*i <= n; j++)
				prime[j*i] = true;
		}
		prime[1] = true; 
		
		for(int i = 2; i <= n; i++)
			if(!prime[i])
				list.add(i);
	}
	public static int countPrime(int n) {
		int sum = 0;
		int count = 0;
		for(int i = 0; i < list.size(); i++) {
			sum = 0;
			for(int j = 0; j < list.size(); j++) {
				if(i + j < list.size()) {					
					sum += list.get(i + j);
					if(sum == n) {
						count++;
						break;
					}
					if(sum > n)
						break;
				}
			}
		}
		return count;
	}
}

소수 판별하는 이중 for문을 저렇게 바뀌어야 시간초과가 안된다...

 

 

(오류코드 : 시간초과)

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

public class Main {

	static int num;
	static ArrayList<Integer> list;
	public static void main(String[] args) throws Exception {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		num = Integer.parseInt(br.readLine());
		fillPrime(num);
//		for(Integer i : list) {
//			System.out.println(i);
//		}
		System.out.println(countPrime(num));
	}
	public static int isPrime(int n) {
		for(int i = 2; i < n; i++) {
			if(n % i == 0)
				return 0;
		}
		return 1;
	}
	public static void fillPrime(int n) {
		list = new ArrayList<Integer>();
		for(int i = 2; i <= n; i++) {
			if(isPrime(i) == 1) {
				list.add(i);
			}
		}
	}
	public static int countPrime(int n) {
		int sum = 0;
		int count = 0;
		for(int i = 0; i < list.size(); i++) {
			sum = 0;
			for(int j = 0; j < list.size(); j++) {
				if(i + j < list.size()) {					
					sum += list.get(i + j);
					if(sum == n) {
						count++;
						break;
					}
					if(sum > n)
						break;
				}
			}
		}
		return count;
	}
}

소수를 판별하는 함수 isPrime

num 안의 소수들이 들어갈 수 있는 ArrayList

그 ArrayList 안의 값들을 더해서 num일때 count++