吸血鬼素数 C/C++

素数 C/C++"/>

吸血鬼素数 C/C++

吸血鬼素数

1994年，美国数学家皮科夫在一篇文章中首次提出了吸血鬼数。如果一个2n（n是自然数）位的自然数等于自己各个数字任意组成的两个n位数的乘积，那么这个自然数就叫吸血鬼数。其中这两个n位数都被称为獠牙或尖牙。比如1260=21×60，所以1260是一个吸血鬼数。注意两个尖牙的个位数不能同时为0，例如虽然126000=210×600，但126000却不是吸血鬼数。在此基础上，2002年，数学家里维拉定义了吸血鬼素数。如果吸血鬼数的两个尖牙都是素数，则这两个尖牙都叫吸血鬼素数。例如，117067=167×701，而167和701都是素数，所以167和701都是3位吸血鬼素数。

输入一个正整数n（小于1000），请判断它是否吸血鬼素数。如果是，打印YES，否则打印NO。

输入格式:

一个小于1000的正整数n

输出格式:

YES或者NO

输入样例:

701

输出样例:

YES

思路：

训练的时候遇到了这题，因为这题的输出只有"YES"和"NO",我直接无脑输出"YES"骗了一点分。‍_(:з」∠)_‍

正常的解法是：
设：i = n*m ,i是吸血鬼数,n是输入的数

先判断n是不是素数，如果不是素数就不可能是吸血鬼素数，直接输出"NO"，结束程序。

如果是素数，则算出n的位数h，根据h得出吸血鬼数i的位数为2h,范围为10^2h-1 <= i < 10^2h,如:n = 701,h = 3,2h = 6,10⁵ <= i < 10⁶,100000 <= i < 1000000。

求出m当且仅当i%n == 0。求出的m也应该是吸血鬼素数，所以还要判断m的位数是否也是h,m是否也是素数。

因为吸血鬼数i等于自己各个数字任意组成的两个n位数的乘积，所以i各个数字出现的次数等于n和m各个数字出现的次数之和。
可以建立两个数组(变量名称是个人习惯)int is[10],nm[10];全部元素初始化为0，分别用来记录i各个数字出现的次数和n和m各个数字出现的次数之和,如果完全相同，就说明n和m是吸血鬼素数。

如果i一直到10^2h都没找到对应的m，则n不是吸血鬼素数。

代码

#include<bits/stdc++.h>
using namespace std;int ss(int x); //判断是不是素数 
int weishu(int x); //计算有多少位 int main(void)
{int n,m;int nm[10],is[10];int h,max_h;int i,j;int z;scanf("%d",&n);if(ss(n) == 1){h = weishu(n);max_h = (int)pow(10,2*h);
//		printf("h = %d\n",h);
//		printf("i = %d\n",(int)pow(10,2*h-1));
//		printf("max_h = %d\n",max_h);for(i = (int)pow(10,2*h-1);i < max_h;i++){if(i%n == 0){m = i/n;if(weishu(m) == h && ss(m) == 1){ //位数相同，都是素数 //printf("%d %d %d\n",i,n,m);for(j = 0;j < 10;j++){nm[j] = 0;is[j] = 0;}while(m > 0){nm[m%10]++;m /= 10;}m = n;while(m > 0){nm[m%10]++;m /= 10;}m = i;while(m > 0){is[m%10]++;m /= 10;}z = 1;for(j = 0;j < 10;j++){if(nm[j] != is[j]){z = 0;break;}}if(z == 1){printf("YES");break;}}}}if(z == 0){printf("NO");}}else {printf("NO");}return 0;
}int ss(int x){int z = 1;int i;if(x == 2){z = 1;}else if(x > 2){if(x%2 == 0){z = 0;}for(i = 3;i <= sqrt(x) && z == 1;i += 2){if(x%i == 0){z = 0;break;}}}else {z = 0;}return z;
}int weishu(int x){int z = 0;if(x != 0){while(x != 0){z++;x /= 10;}}else {z = 1;}return z;
}