农夫约翰想从正整数AB之间选一些质数来作为奶牛的编号 ，并且作为编号的数各位上的数字至少有一个特定的数字D。如A为10、B为15、D为3时，AB之间有11、13两个素数，但组成11的两个数字中没有3，所以只有一个数13符合条件。
输入描述
一行三个正整数A、B、D，之间用一个空格隔开。 其中1<=A<=B<=4000000，B<=A+2000000，0<=D<=9
输出描述
一行一个正整数，表示包含数字D的质数个数
样例输入
10 15 3
样例输出
1
#include <stdio.h>
int prime[2000001], D, sum = 0;
bool vis[4000001];
int main() {
int A, B, cnt = 0;
int check(int);
scanf("%d%d%d", &A, &B, &D);
memset(vis, false, sizeof(vis));
for (int i = 2; i <= B; i++) {
if (!vis[i]) {
prime[cnt++] = i;
if (i >= A) sum = sum + check(i);
}
for (int j = 0; j < cnt && iprime[j] <= B; j++) {
vis[iprime[j]] = true;
if (i % prime[j] == 0) break;
}
}
printf("%d\n", sum);
return 0;
}
int check(int x) {
while (x) {
if (x % 10 == D) return 1;
x /= 10;
}
return 0;
}
首先判断一个数字是否为质数，使用了最简单的试除法。
然后，判断一个数字是否包含特定数字D，这里用到了取模和取整操作。
最后，遍历AB之间的所有数字，判断是否为质数且包含特定数字D即可。
以下是代码：
#include <stdio.h>
#include <stdbool.h>
bool is_prime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
bool contain_digit(int n, int d) {
while (n) {
if (n % 10 == d) {
return true;
}
n /= 10;
}
return false;
}
int main() {
int A, B, D;
scanf("%d %d %d", &A, &B, &D);
int count = 0;
for (int i = A; i <= B; i++) {
if (is_prime(i) && contain_digit(i, D)) {
count++;
}
}
printf("%d\n", count);
return 0;
}
输入要求的10 15 3检验了一下
输出
1
在 10 和 15 之间，只有 13 是质数且包含数字 3，因此计数器 count 值为 1
以下是使用C语言解决该问题的代码，其中使用了一个is_prime函数来判断一个数是否为质数。具体解释见代码注释。
#include <stdio.h>
#include <stdbool.h>
// 判断是否为质数
bool is_prime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int A, B, D;
scanf("%d %d %d", &A, &B, &D);
int count = 0; // 记录符合条件的质数个数
for (int i = A; i <= B; i++) {
if (is_prime(i)) { // 如果i是质数
int temp = i;
while (temp) { // 遍历i中的每一位
if (temp % 10 == D) { // 如果这一位是D
count++; // 计数器加1
break; // 跳出循环
}
temp /= 10;
}
}
}
printf("%d", count);
return 0;
}
该代码的思路是，先定义一个is_prime函数来判断一个数是否为质数。然后在主函数中，读入A、B、D三个数，然后从A到B遍历每一个数，如果这个数是质数，就遍历这个数的每一位，如果这一位是D，就把计数器加1。最后输出计数器的值即可。
以下是求解此问题的 C 语言代码示例。其中，关键算法为判断素数和判断是否包含数字 D。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
// 判断数字 n 是否为素数，是则返回 true，否则返回 false
bool IsPrime(int n) {
if (n == 2 || n == 3) { // 特殊情况下的素数
return true;
}
if (n <= 1 || n % 2 == 0 || n % 3 == 0) { // 排除一些非素数情况
return false;
}
int i = 5;
while (i * i <= n) { // 判断是否存在小于等于 sqrt(n) 的因子
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
i += 6;
}
return true;
}
// 判断数字 n 中是否包含数字 d，是则返回 true，否则返回 false
bool ContainsD(int n, int d) {
while (n > 0) {
if (n % 10 == d) {
return true;
}
n /= 10;
}
return false;
}
int main() {
int A, B, D;
scanf("%d %d %d", &A, &B, &D);
int count = 0; // 包含数字 D 的质数的个数
for (int i = A; i <= B; i++) {
if (IsPrime(i) && ContainsD(i, D)) {
count++;
}
}
printf("%d\n", count);
return 0;
}
通过此代码，您可以输入正整数 A、B 和数字 D，并得到包含数字 D 的质数的个数。请注意，在判断是否为素数和是否包含数字 D 的函数中，可以根据具体问题进行优化，以获得更好的性能。
您可以使用以下算法来解决这个问题：
首先，您可以编写一个函数来判断一个数是否为质数。您可以使用最简单的方法：从2到sqrt(n)枚举所有的数，如果n可以被其中的任意一个数整除，则n不是质数，否则n是质数。
然后，您可以编写一个函数来判断一个数是否包含特定的数字D。您可以将该数转换为字符串，然后检查该字符串中是否包含字符D。
最后，您可以在A和B之间枚举所有的数，并使用上述两个函数来判断每个数是否为质数且是否包含数字D。如果该数是质数且包含数字D，则将计数器加1。
下面是一个可能的C语言实现：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int is_prime(int n) {
if (n < 2) return 0;
int i;
for (i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return 0;
}
return 1;
}
int contains_digit(int n, int d) {
char str[10];
sprintf(str, "%d", n);
return strchr(str, '0' + d) != NULL;
}
int main() {
int a, b, d;
scanf("%d%d%d", &a, &b, &d);
int count = 0;
int i;
for (i = a; i <= b; i++) {
if (is_prime(i) && contains_digit(i, d)) {
count++;
}
}
printf("%d\n", count);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int prime[2000001],D,sum=0;
bool vis[4000001];
int main()
{
int A,B,cnt = 0;
int check(int );
cin>>A>>B>>D;
memset(vis, false, sizeof(vis));
for(int i = 2; i <= B; i++)
{
if(!vis[i])
{prime[cnt++] = i;if(i>=A) sum=sum+check(i);}
for(int j = 0; j<cnt && iprime[j]<=B; j++)
{
vis[iprime[j]] = true;
if(i%prime[j] == 0) break;
}
}
cout<<sum;
return 0;
}
int check(int x)
{
while(x)
{
if(x%10==D) return 1;
x/=10;
}
}
参考代码
#include <stdio.h>
#include <stdbool.h>
// 判断一个数是否为质数（素数）
bool is_prime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= num / i; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
int A, B, D;
scanf("%d%d%d", &A, &B, &D);
int count = 0; // 统计个数
for (int i = A; i <= B; i++) {
if (is_prime(i)) { // 是否为质数
int num = i;
// 判断是否包含数字 D
while (num > 0) {
if (num % 10 == D) { // 数字 D 包含在数中
count++;
break;
}
num /= 10;
}
}
}
printf("%d\n", count);
return 0;
}