글 읽기 - 시간초과

juwqq1234 1년 전 0

에라토스테네스의 체 사용했습니다

예제출력도 잘되는데 시간초과라고뜨네요 엉엉

혹시반례가 있나요?

#include<stdio.h>
#include<math.h>
int A[300000];
int sosu(int A) //소수인경우에는 1을반환,소수가 아닌경우에는 0을반환하는 함수
{   int t = 0;
	for (int j = 1; j <= A; j++) {
		if ((A % j) == 0)
			t++;}
	if (t == 2)//소수이다
		return 1;
	else //소수가 아닌경우  //t!=2인경우
		return 0;}

int main(void) {
	for (int k = 0; k < 300000; k++) {
		A[k] = k;}
     while (1) {
		int n, count=0;
		scanf("%d",&n);
		int S[491]={0};
		if (n == 0)
			return 0;
		for (int i = 1,t=0; i <= (int)sqrt(2*n); i++)
		{
			if (sosu(i) == 1)
			{
				S[t] = i;
				t++;
			}  
		}  //S는 2n까지의 소수의배열   >>에라토스테네스의 채 소수가아닌것을 골라내는것
		for (int i = 0; S[i] != 0; i++)
		{
			for (int j = n + 1; j<= 2 * n; j++) {
				if (j % S[i] == 0 && j != S[i])  //이조건에 걸리면 소수가 아니다 
				{
					A[j] = 0;
				}
			}
         }
		for (int j = n + 1; j <=2 * n; j++) {
			if (A[j] != 0)
				count++;
		}
		
		printf("%d\n", count);
	}
	return 0;
}

seawon0808 1년 전 1

소수 빨리 구하는 방법을 알아보세요.

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

문제

문제

출처

ICPC

시간초과

juwqq1234 1년 전 0

seawon0808 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말