用C语言编程,给定一个整数N(2 <= N <= 8),生成所有的具有下列特性的特殊的N位质数,即其前任意位都是质数。例如,7331即是这样一个4位的质数,因为7、73和733也都是质数。 【输入形式】 输入一个整数N(2 <= N <= 8)。 【输出形式】 输出有若干行,每行有一个整数,该整数有N位,而且其前任意位都是质数。并且: 1.要求输出所有符合题意的质数。 2.从小到大按顺序输出,且所有行上的数字不得重复。
时间: 2024-02-27 17:59:01 浏览: 67
c语言输出N位质数
以下是用C语言编写的程序,可以实现该功能:
```
#include<stdio.h>
#include<math.h>
#define MAX 1000000000
int primes[MAX]; //存储所有的质数
int digits[MAX]; //存储数字的每一位
int n, count; //n表示位数,count表示符合要求的质数的个数
//判断一个数是否是质数
int is_prime(int num) {
if (num == 2) return 1;
if (num % 2 == 0) return 0;
int sqr = sqrt(num);
for (int i = 3; i <= sqr; i += 2) {
if (num % i == 0) return 0;
}
return 1;
}
//将数字的每一位存储到数组中
void get_digits(int num) {
int i = 0;
while (num) {
digits[i++] = num % 10;
num /= 10;
}
for (int j = i; j < n; j++) digits[j] = -1; //不足n位的用-1填充
}
//判断前k位数字是否是质数
int is_prime_prefix(int k) {
int num = 0;
for (int i = k - 1; i >= 0; i--) {
num = num * 10 + digits[i];
if (!is_prime(num)) return 0;
}
return 1;
}
//搜索符合要求的数字
void search(int k, int num) {
if (k == n) {
if (is_prime(num)) {
printf("%d\n", num);
count++;
}
return;
}
for (int i = 1; i < 10; i += 2) { //只考虑奇数
digits[k] = i;
if (is_prime_prefix(k + 1)) {
search(k + 1, num * 10 + i);
}
}
digits[k] = -1;
}
int main() {
scanf("%d", &n);
primes[2] = 1;
for (int i = 3; i < MAX; i += 2) { //只需要考虑奇数
primes[i] = is_prime(i);
}
search(0, 0);
return 0;
}
```
该程序中,我们首先用数组`primes`存储所有的质数,这样可以避免重复计算。然后,我们将数字的每一位存储到数组`digits`中,用函数`is_prime_prefix`判断前k位数字是否是质数,用函数`search`递归搜索符合要求的数字,最后输出所有的符合要求的质数。
需要注意的是,在判断前k位数字是否是质数时,我们是从高位到低位依次判断,这样可以避免重复计算。另外,我们只需要考虑奇数,因为偶数肯定不是质数。
阅读全文