글 읽기 - 시간초과때문에.. 시간을 줄일 방법이 없을까요..?(JAVA)

xovndrkd 5년 전 0

바로 아랫글 java로한것도 체크해보았는데 저와는 풀은 방식이 달라서 질문 올리게 됬습니다.!

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scan = new Scanner(System.in);
		ArrayList<Integer> arr = new ArrayList<>();
		int ans = 0;
		
		while(true)
		{
			int n = scan.nextInt();
			if(n == 0)
				break;
			arr.add(n);
		}
		scan.close();
		int size = arr.size();
		int index =0;
		while(index < size)
		{
			int num = arr.get(index);
			for(int i=2*num;i>num;i--)
			{
				if(isSosu(i))
					ans+=1;
			}
			System.out.println("index ="+index+ " -> "+ans);
			ans = 0;
			index += 1;
		}
	}
	static boolean isSosu(int num)
	{
		int count = 0;
		if(num == 0)
			return false;
		for(int i=num;i>0;i--)
		{
			if(num % i == 0)
			{
				count += 1;
			}
		}
		if(count == 2)
			return true;
		else
			return false;
	}
}

surung9898 5년 전 3

소수 판정에 있어서, 어떤 자연수 n을 판정하는 기준으로 보통 'n이 2부터 sqrt(n)까지의 수 중 하나로 나누어 떨어지는가'를 보통 채택합니다. 예시로, 32가 소수인지를 판정할 때에는 32를 2부터 5까지만 나누어 볾으로써 소수를 판정할 수 있습니다.

간략하게 설명드리자면, 32의 약수는 각각 1 2 4 8 16 32이므로, 32를 4를 나누어 보는 것과 8을 나누어 보는 것에는 차이를 가지지 않는다는 것입니다.

따라서 TC를 줄이기 위해서, isSosu 함수 부분의 소수 판정 구문과 그에 따른 주변 코드도 수정하시면 될 것 같습니다.

xovndrkd 5년 전 1

조언 감사드립니다. 덕분에 풀었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과때문에.. 시간을 줄일 방법이 없을까요..?(JAVA)

xovndrkd 5년 전 0

surung9898 5년 전 3

xovndrkd 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말