글 읽기 - 1990 95퍼센트에서 출력초과입니다

supernova 9년 전 0

으아아아아아아아아아아ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#include<stdio.h>

bool isNotPrime[100000011];

bool isPal(int inputNum){
	if(inputNum < 10 ) return true;

	long long int i;
	for(i = 1;i <= inputNum ; i *= 10);

	long long int left = i/10 , right = 1 ,leftNum, rightNum;

	for(; left > right ; left /= 10 , right *= 10){
		leftNum = (inputNum % (left * 10)) / left;
		rightNum = (inputNum % (right * 10)) / right;

		if(leftNum != rightNum)
			return false;
	}

	return true;
}

void getPrime(){
	int num = 2;
	for( ; num < 10000011 ; num++){

		if(isNotPrime[num] == true) continue;

		for(int j = num + num; j < 10000011; j += num)
			isNotPrime[j] = true;
	}
}

int main(){
	getPrime();

	int firNum, secNum;
	scanf("%d %d",&firNum, &secNum);

	for(int i = firNum ; i <= secNum ; i++){
		bool pal = isPal(i);
		if( pal == true && isNotPrime[i] == false)
			printf("%d\n",i);
	}
	printf("-1");

	return 0;
}

baekjoon 9년 전 0

일단 이 방법은 시간 초과가 날 거 같긴 한데...

그리고, bool을 사용했을 때, 변수명에 not을 붙이는 것은 좋지 않아요.

isNotPrime[i] = true; 보다는 isPrime[i] = false;가 좋지요.

pichulia 9년 전 2

8자리 이상의 소수에는 소수팰린드롬이 없다는걸 발견한건 잘했습니다.

하지만 현재 코드에선 secNum이 10000011 보다 크게 들어오는 경우 문제가 발생하네요

10^7 이상의 모든 숫자가 소수라고 판정되고있기 때문입니다.

if(secNum > 10000000) secNum = 10000000;

이 부분을 추가한다면 문제없이 맞을 수 있을겁니다.

Hibbah 9년 전 0

갓츄리엘.....

supernova 9년 전 0

헐 그럴수가 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ 치명적인 실수였네요 ㅠㅠㅠㅠ

@pichulia님 감사합니다

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

문제

문제

출처

ICPC

1990 95퍼센트에서 출력초과입니다

supernova 9년 전 0

baekjoon 9년 전 0

pichulia 9년 전 2

Hibbah 9년 전 0

supernova 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말