[백준풀이] 17103소수 전처리

풀코드

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

public class Gold 
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		boolean[] list = new boolean[1000001];
		Arrays.fill(list, true);
		list[1]=false;
		list[0]=false;
		
		int[] list2 = new int[1000001];
		int list2_idx=0;
		for(int i=2;i<= 1000000;i++)
		{
			if(list[i])
			{
				list2[list2_idx++]=i;
				for(int j=i+i;j<=1000000;j+=i )
				{
					list[j]=false;
				}
			}
		}
		//System.out.println("list2[0]:"+list2[0]);
		
		
		int num = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++)
		{
			int N = Integer.parseInt(br.readLine());
			int round_result=0;
			for(int j=0;j<=N/2;j++)//숫자 N보다 작은 숫자들중 소수만 골라내기
			{
				if(list[j]&&list[N-j])//둘다 소수라면
					round_result++;
					
			}
			sb.append(round_result+"\n");
		}
		
		System.out.println(sb);
	}
}

풀이

먼저 에라토스테네스의 체로 전처리하자 정수의 범위가 100만이므로 100만+1만큼 배열크기를 잡아주고 에라토스 테네스의 체를 돌리자(전처리)

https://velog.io/@holy38/%EC%BD%94%EB%93%9C-%EB%B6%84%EC%84%9D-%EB%B0%B1%EC%A4%801929-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4ArrayIndexOutofBounds --> 에라토스테네스의 체

1. N/2를하여 순서만 다른 파티션 배제한다.
2. j + ( N - j ) = N 이다
   
   
   

시간 초과난 코드

list2에 소수만 따로 저장해놓은뒤 각 케이스마다 2중 for문을 돌려서 그런지 시간초과가 난다.
참고만 하시길

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

public class Main
{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		boolean[] list = new boolean[1000001];
		Arrays.fill(list, true);
		list[1]=false;
		list[0]=false;
		
		int[] list2 = new int[300000];
		int list2_idx=0;
		for(int i=2;i<= 1000000;i++)
		{
			if(list[i])
			{
				list2[list2_idx++]=i;
				for(int j=i+i;j<=1000000;j+=i )
				{
					list[j]=false;
				}
			}
		}
		//System.out.println("list2[0]:"+list2[0]);
		
		
		int num = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++)
		{
			int N = Integer.parseInt(br.readLine());
			int round_result=0;
			for(int j=0;list2[j]<N;j++)
			{
				for(int q=j;list2[q]<N;q++)
				{
					if(list2[j]+list2[q]==N)
					{
						round_result++;
							//System.out.println("j:"+list2[j]+"\nq:"+list2[q]);
					}		
				}
			}
			sb.append(round_result+"\n");
		}
		
		System.out.println(sb);
	}
}