素数问题

柔光的暖阳◎ 2022-05-19 09:26 294阅读 0赞

素数又称为质数即除了1和本身，不能够被其他数整除.1不是素数。

判断一个数n是否为素数，只需要判断n是否能够被2和![b03533fa828ba61e582843574234970a314e5980.jpg][] 之间的数整除。

当然，这个过程可以进一步优化步骤，比如说判断到![b03533fa828ba61e582843574234970a314e5980.jpg][] 就行了是一个优化。当然可以先判断这个数是不是大于2的偶数，如果是的话就可以直接输出不是质数了。对于为什么可以运算到![b03533fa828ba61e582843574234970a314e5980.jpg][] 即可判断这个数是不是偶数，原因可能有点麻烦。

设d>![b03533fa828ba61e582843574234970a314e5980.jpg][] ,并且n%d=0；

那么n/d<![b03533fa828ba61e582843574234970a314e5980.jpg][] ,n%(n/d)=0;

所以，如果n可以整除一个大于![b03533fa828ba61e582843574234970a314e5980.jpg][] 的数，那么也可以整除一个小于![b03533fa828ba61e582843574234970a314e5980.jpg][] 的数。

给出N个正整数，检测每个数是否为质数。如果是，输出"Yes"，否则输出"No"。

Input

第1行：一个数N，表示正整数的数量。(1 <= N <= 1000)   
第2 - N + 1行：每行1个数(2 <= Sii <= 10^9)

Output

输出共N行，每行为 Yes 或 No。

Sample Input

5
    2
    3
    4
    5
    6

Sample Output

Yes
    Yes
    No
    Yes
    No

#include <stdio.h>
    int isprime(int n)
    {
    	if(n==1)
    		return 0;
    	if(n&0)   //判断是不是偶数 
    		return 0;
    	for(int i=2;i*i<=n;i++)
    	{
    		if(n%i==0)
    			return 0;
    	}
    	return 1;
    }
    int main()
    {
    	int n,t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		printf("%s\n",isprime(n)?"YES":"NO");
    	}
    	return 0;
    }

### 筛素数法 ###

简单地说就是把不是素数的数先筛选出来。可以先创建一个数组。比如说a\[2\]，2是素数，所以a\[2\]为0；4不是素数，所以a\[4\]=1;要判断那些数是素数很简单。直接把2的倍数，3的倍数，4的倍数直接标记为1即可。

把一个偶数拆成两个不同素数的和，有几种拆法呢？

Input

输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。

Output

对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。

Sample Input

30
    26
    0

Sample Output

3
    2

#include <stdio.h>
    int main()
    {
    	int a[10005];
    	int n;
    	int i,j;
    	for(i=2;i*i<=10005;i++)
    		if(a[i]==0)
    			for(j=i*i;j<=10005;j+=i)
    				a[j]=1;
    	while(scanf("%d",&n)&&n)
    	{
    		int cnt=0;
    		for(int i=2;i<n/2;i++)
    		{
    			if(a[i]!=1&&a[n-i]!=1)
    				cnt++;
    		}
    		printf("%d\n",cnt);
    	}
    	return 0;
    }

[b03533fa828ba61e582843574234970a314e5980.jpg]: https://gss0.bdstatic.com/94o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D21/sign=290269626359252da7171a05359bf970/b03533fa828ba61e582843574234970a314e5980.jpg