首页 > 代码库 > 高速查找素数

高速查找素数

2024-10-06 02:31:39   215人阅读

高速查找素数

时间限制：1000 ms  |  内存限制：65535 KB
难度：3
描写叙述
如今给你一个正整数N，要你高速的找出在2.....N这些数里面全部的素数。

输入
给出一个正整数数N(N<=2000000)
但N为0时结束程序。
測试数据不超过100组
输出
将2~N范围内全部的素数输出。两个数之间用空格隔开
例子输入
5
10
11
0
例子输出
2 3 5
2 3 5 7
2 3 5 7 11
来源
经典题
上传者

路过这

素数打表。提交開始超时。改成c语言的就过了

 
#include<iostream>
#include<string.h>
#include<math.h>
#include<stdio.h>
using namespace std;
int a[2000001];
void sushu()
{
	int i,j;
	a[0]=a[1]=1;
	for(i=2;i<=sqrt(2000000);i++)
	{
		if(a[i]==0)
		{
			for(j=i*i;j<=2000000;j+=i)
			{
				a[j]=1;
			}
		}
	}
}
int main()
{
	sushu();
	int N,i,time;
	while(scanf("%d",&N) && N)
	{
		time=0;
		if(N>=2)
		   printf("2");
         for(i=3;i<=N;i++)
		 {
			 if(a[i]==0)
				 //cout<<" "<<i;
				printf(" %d",i);
		 }
		 cout<<endl;
	}
	return 0;
}

高速查找素数


联系
我们