글 읽기 - 시간초과라고 뜨는데.. 너무 많이 돌려서인 걸까요?!

shg789 9년 전 0

N자리수에 대한 소수에 중 신기한 소수를 찍어주는 소스인데..

N자리에 대한 소수를 찾으면서 신기한 소수를 찾을 때 포문이 너무 돌아가서 시간초과인 건가요? ㅠㅠ

아니면 다른 방법으로 풀어야하나요 ㅠㅠ?

알려주시면 감사하겠습니다~ ^^

import java.util.Scanner;
 
class Main {
    public static void main(String args[]){
        int i,j,N,p=1;
        Scanner s = new Scanner(System.in);
        N=s.nextInt();
        for(i=2; i<=N; i++) p*=10;
 
        for(i=p; i<p*10; i++){
            if(pn(i)){
                int m=1;
                for(j=1; j<N; j++,m*=10){
                    if(i/(p/m)!=1 && pn(i/(p/m))){
                        if(j==N-1) System.out.println(i);
                        continue;
                    }
                    else break;
                }
            }
        }
    }
    //소수인지 판별하는 메소드
    public static boolean pn(int n){
        int i;
        for(i=2; i<=n; i++){
            if(i==n) return true;
            if(n%i==0) return false;
        }
        return false;
    } 
}

hahaha 9년 전 0

넵 너무 많은 시간이 걸리는 방법이에요 ㅠ ㅠ

N자리의 모든 수가 소수인지 확인하니 너무 오래걸리네요. n자리의 수가 소수인지 확인하는 for문이 한번에 n번이니 N이 8이면 그 한번의 확인도 10^8이네요..

다른 방법을 생각해 보세요 :)

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

문제

문제

출처

ICPC

시간초과라고 뜨는데.. 너무 많이 돌려서인 걸까요?!

shg789 9년 전 0

hahaha 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말