글 읽기 - 소수 찾기: 윌슨의 정리 가지고 코드를 짰는데 왜 틀리죠?(Java)

drasein 3년 전 0

간단하게 말하면, 윌슨의 정리에서는 수가 소수인걸을 판별하는 법은 (n-1)!%n == n-1인데 무언가 잘못된가요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {
	//윌슨의 정리를 이용하여
	
	static int factorial(int num) {//factorial
		if(num==0) {
			return 1;
		}else {
			return num*factorial(num-1);
		}
	}
	
	static int isPrime(int num) {//count primes
		int fact_num = factorial(num-1);
		int count = 0;
		if(fact_num%num == num-1&&num!=1) {
			count += 1;
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		int times = 0;
		int[] nums;
		String[] holder;
		int count = 0;
		
		//initializing nums array
		times = Integer.parseInt(in.readLine());
		nums = new int[times];
		holder = in.readLine().split(" ");
		
		//Counting primes
		for(int i=0;i<times;i++) {
			nums[i] = Integer.parseInt(holder[i]);
			count += isPrime(nums[i]);
		}
		
		//printing result
		out.write(count+"");
		out.flush();
		/* 
		 * 1. factorial func
		 * 2. (n-1)!%n == n-1?: count++;
		 * 3. return & print count
		 */
	}

}

djm03178 3년 전 0

1000!은 평범한 int에 담을 수 없을 정도로 큽니다. long으로도 턱없이 모자랍니다.

drasein 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

소수 찾기: 윌슨의 정리 가지고 코드를 짰는데 왜 틀리죠?(Java)

drasein 3년 전 0

djm03178 3년 전 0

drasein 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말