글 읽기 - 골드바흐의 추측...

zayne 8년 전 0

이거 며칠째 왜 안되는지 고민했는데

시간초과 뜨다가(받는값의 최대의 양의 제곱근까지 일일히 나눠서 판별)

에라토스체로 소수판별을 바꾸고.

런타임에러 뜨다가(이유는 모르겠지만 전체수와 소수배열을 전역에서 지역으로 내리니 해결)

다시 시간초과 떠서 같은 구조에서 연산수를 꽤 줄이도록 해서 냈더니

현재는 출력초과가 뜨고 있습니다.

잘 생각해봐도 아직도 잘 모르겠어서 이제는 SOS쳐봅니다.

고수님들 지적 부탁드려요. (왜 초과가 뜨는지 / 소수배열 생성을 처음시도했던 양의제곱근까지 나누기로 한다던가)

주석은 최대한 자세히 써봤습니다.

#include <stdio.h>

int Is_Prime(int n,int t,int p_set[]); //소수 배열에서 소수여부 확인 함수.

int main(void)
{
    int Num_Sets[999999]={0};//전체수 연산후 값이 0이면 소수취급.
	int Prime_Sets[80000];//소수집합 백만까지 소수 80000개 이하.
	int Prob_Sets[100];//인풋
	int Ans_Sets[100];//아웃풋
	int i,j,k;
	int max=0;//인풋중 최대값 
	int count=0;

	//0나올때까지 받기
	i=0;
	while(1){
		scanf("%d",&Prob_Sets[i]);
		if(Prob_Sets[i]>max)
			max=Prob_Sets[i];
		if(Prob_Sets[i++]==0)//0나오면 그만 받는다.
			break;
	}

	//전체수의 배열에 수 입력와
	for(i=3;i<=max;i+=2)//2배수와 1 이런거는 선언시 0이므로 3+2n만 숫자입력/직관적으로 보이게 인덱스=실제값
		Num_Sets[i]=i;
	for(i=3;3*i<=max;i+=2){ //밑에서 3i 5i 7i이런식으로 비교하므로  i는 최대의 1/3이면 족함. 하지만 이중포문
		if(Num_Sets[i]==0)//이미 0으로 소수판별됬으면 연산하지 말자.
			continue;
		for(j=3*i;j<=max;j+=2*i)//i는 소수가 아니고 2의배수는 이미 쳐냈으니 3i 5i 7i.... so on은 합성수이므로 0으로
			Num_Sets[j]=0;
	}

	j=0;
	for(i=3;i<=max;i+=2)//0이 아니라 살아남은 아이들 소수배열에 저장. 2는 의미없고 홀수 소수만 고려
		if(Num_Sets[i]!=0)
			Prime_Sets[j++]=Num_Sets[i];

	//합 찾기, j는 현재 찾은 개수의 지표
	count=0;
	i=0;
	while(Prob_Sets[i]!=0){
        if(Prob_Sets[i]%2==1){//홀수받은 예외처리
            i++;
            continue;
        }
		for(k=0;k<j;k++){//여기도 isprime과 이중포문.....
			if(Is_Prime(Prob_Sets[i]-Prime_Sets[k],j,Prime_Sets)){//문제-소수가 소수이면
				Ans_Sets[i]=Prime_Sets[k]; //그 가장 작은 소수를 답 배열에 넣는다.
				count++;
				break; //더 큰거 찾기전에 나간다.
			}
		}
		if(count==0) // 못찾으면 -1을 예외로 두고
			Ans_Sets[i]=-1;
		count=0;
		i++;
	}

	//출력하기
	i=0;
	while(Prob_Sets[i]!=0){
		if(Ans_Sets[i]==-1||Prob_Sets[i]%2==1) // 답배열에서 위에 했던대로 -1뜨면 골드바흐는 틀렸다.+홀수예외처리
			printf("Goldbach's conjecture is wrong.\n");
		else// 아니면 답을 배출.
			printf("%d = %d + %d\n",Prob_Sets[i],Ans_Sets[i],Prob_Sets[i]-Ans_Sets[i]);
		i++;
	}
	return 0;
}
int Is_Prime(int n,int t,int p_set[]) // n이 소수인지 판별 소수배열의 개수가 t개일떄 소수면 1 리턴 아니면 0리턴
{
	int i,k;
	k=0;
	for(i=t-1;i>=0;i--)
		if(n==p_set[i]){
			k++;
			break;
		}
	if(k)
		return 1;
	else
		return 0;
}

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

문제

문제

출처

ICPC

골드바흐의 추측...

zayne 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말