算法竞赛--素数

发表于 更新于 分类于 阅读次数：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

素数的判断

1
2
3
4
5
6
7
8
9
bool isPrime(int a)
{
	if(a<=1)
		return false;
	for(int i=2;i*i<=a;i++)
		if(a%i==0)
			return false;
	return true;
}

素数表的获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPrime(int a)
{
	if(a<=1)
		return false;
	for(int i=2;i*i<a;i++)
		if(a%i==0)
			return false;
	return true; 
}
int find(int n)
{
	int count=0;
	for(int i=1;i<=n;i++)
		if(isPrime(i))
			p[count++]=i;
	return count;	
}

埃氏筛法

思路:算法从小到大枚举所有数，对每一个素数，筛去它的所有倍数，剩下的就都是素数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(int n)
{
	int count=0;
	for(int i=2;i<n;i++)
	{
		if(prime[i]==false)
		{
			p[count++]=i;
			for(int j=i+i;j<n;j=j+i)
				prime[j]=true;
		}
	}
	return count;
}

素数

输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。

输入:

输入有多组数据。

每组一行，输入n。

输出:

输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。

样例输入:

1
70

样例输出:

1
11 31 41 61

思路:利用埃氏筛法求出10000以内的素数，再在n的范围内进行判断，输出个位为1的素数

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
bool prime[10010]={0};
int p[10010],a[10010];
void find()		//埃氏筛法求10010内的素数
{
	int count=0;
	for(int i=2;i<10010;i++)
	{
		if(prime[i]==false)
		{
			p[count++]=i;
			for(int j=2*i;j<10010;j=j+i)
				prime[j]=true;
		}
	}	
}
int main()
{
	int n;
	find();
	while(scanf("%d",&n)==1)
	{
		int c=0;
		for(int i=0;p[i]<n;i++)
			if(p[i]%10==1)
				a[c++]=p[i];		//a中存放符合条件的素数
		if(!c)
		{
			printf("-1\n");
			continue;
		}
		for(int i=0;i<c-1;i++)
			printf("%d ",a[i]);
		printf("%d\n",a[c-1]);		
	}
	return 0;
}
小礼物走一个哟
0%