【每日一题C】#188. 指定范围内的质数

女爷i 2023-10-11 17:31 3阅读 0赞

**一、**

**题目：**

我们都知道，对于一个大于 1的整数，如果除了 1和它本身，它不再被其它正整数整除，那么我们说它是一个质数。请对于给定的一个大于 1的正整数 N（你可以认为测评机给出的 N均小于等于10^6），和一个大于 1的正整数 M（你可以认为测评机给出的 M均小于等于 10^6 ）， N一定大于 M，请按从小到大的顺序输出所有小于等于 N 且大于等于 M的质数。

**思路：**

1、利用素数筛的方法，先定义一个数组prime\[MAX\_N\]并将其初始化为0；

2、用prime\[0\]存放素数的个数，素数从2开始，每发现一个素数，prime\[0\]数量加一，该数量也可以作为存放素数的数组下标，即该素数赋值给prime\[prime\[0\]\]；

3、当j\*i较小时，可以发现prime\[j\*i\]=1的值1因prime\[++prime\[0\]\]变成素数值，但不用担心，因为每一趟循环j\*i都会大于++prime\[0\]的值，prime\[j\*i\]=1只是作为判断是否要continue的依据，若为1时continue，则后面的语句不被执行，直接转到下一个循环，直到prime\[j\*i\]=0取到素数i。

4、当程序结束后，prime\[0\]值为小于等于10^6的所有素数个数。

**代码：**

#include<stdio.h>
    #define MAX 1000000
    int prime[MAX+5]={0};
    void fun(){
    	for(int i=2;i<=MAX;i++){
    		if(prime[i])continue;
    		prime[++prime[0]]=i;//prime[0]用来记录素数的个数
    		for(int j=i,I=MAX/i;j<=I;j++){
    			prime[j*i]=1;
    		}
    	}
    return ;
    }
    int main(){
    	fun();
    	int n,m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=prime[0]&&prime[i]<=n;i++){
    	   if(prime[i]<m) continue;
    		printf("%d\n",prime[i]);
    	}
    	return 0;
    }

**运行结果示例：**

30 5
    5
    7
    11
    13
    17
    19
    23
    29

**二、**

**题目：**

给定两个四位正整数 a,b，找出这两个数之间（含）所有满足以下条件的数：

1.这个四位数是质数；

2.千位数字与百位数字构成的两位数 AB是一个完全平方数；

3.十位数字与个位数字构成的两位数 CD 是一个完全平方数。

**输入**

输入两个四位正整数 a,b。（1000≤a<b≤9999）

**输出**

输出两行。

第一行为从 a到 b之间所有满足条件的数，两个数字之间用空格隔开，最后一个数后没有空格。

第二行为满足条件的数的个数 n。

**代码：**

#include<stdio.h>
    #include<math.h>
    int fun(int n){//完全平方数判断
    	int a,b,i,j,k=0;
    	a=n/100;//前两位
    	b=n%100;//后两位
    	i=sqrt(a);
    	j=sqrt(b);
    	if(i*i==a&&j*j==b) return 0;
    	return 1;
    }
    void  prime(int a,int b){//质数判断
    	int n[10000]={0},k=0;
    	for(int i=2;i<=b;i++){
    		if(n[i]) continue;//非质数
    		n[i]=1;
    		n[++n[0]]=i;//n[0]记录质数个数
    		for(int j=2;j*i<=b;j++)
    			n[j*i]=1;
    	}
    	for(int i=1;i<=b&&i<=n[0];i++){
    		if(a>n[i]) continue;
    		if(fun(n[i])) continue;
    		if(k)
    			printf(" ");
    		printf("%d",n[i]);
    		k++;
    	}
    	printf("\n%d\n",k);
    }
    int main(){
    	int a,b;
    	scanf("%d%d",&a,&b);
    	prime(a,b);
    	return 0;
    }

**输入输出示例**

1000 2000
    1601 1609
    2