소수 찾기 (소수표)

빠른 찾기 소수
시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
3

묘사
지금 너에게 정수 N을 하나 줄게. 빨리 2에 찾아내라고...N 이 수 안에 있는 모든 소수.

입력
양의 정수 N (N<=2000000) 을 제시합니다.
그러나 N은 0으로 프로그램을 종료합니다.
테스트 데이터가 100 그룹을 넘지 않음
출력
2~N 범위의 모든 소수를 출력한다.두 수 사이를 빈칸으로 나누다
샘플 입력

샘플 출력

2 3 5
2 3 5 7
2 3 5 7 11

제목:
0이 끝날 때까지 N(1~20000000)을 입력합니다.2에서 N 범위의 모든 소수를 출력합니다.

아이디어:
일반적인 방법으로는 반드시 TLE가 될 것이기 때문에 소수표를 만들어서 2에서 N까지 소수의 전부를 표시해야 한다.

AC:

#include<stdio.h>
#include<string.h>
#define MAX 2000000
int num[MAX];

void makeprime()
{
	memset(num,0,sizeof(num));
	for(int i=2;i<=1000000;i++) //     
		{
			if(!num[i])
			{
				for(int j=i+i;j<=MAX;j+=i)  //   i+i  
					 num[j]=1;
			}
		}
	return;
}
//1      ，0     
int main()
{
	int n;
	makeprime();
	while(scanf("%d",&n)!=EOF&&n)
	{
		printf("%d",2);
		for(int i=3;i<=n;i++)
			 if(!num[i]) printf(" %d",i);
		printf("
");
	}
	return 0;
}

요약:
1.롱롱을 사용하면 시간을 초과할 수 있고 int로 충분합니다.
2.배불리 먹고 버티는 문제...

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ] 2581번 소수

<< 문제 클릭! 입력 : 자연수 M, N (M, N은 10,000 이하의 자연수, M은 N보다 작거나 같다) 자연수 M이상 N 이하의 자연수 중 소수를 모두 찾는다. : 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

소수 찾기 (소수표)

좋은 웹페이지 즐겨찾기