判断18位以内的数是否为素数 较大数质数判定
发布时间:2020-12-14 01:56:14 所属栏目:大数据 来源:网络整理
导读:#includestdio.h #includestdlib.h #includetime.h #includemath.h #define M 12 unsigned long long int Pr(unsigned long long int a,unsigned long long int b,unsigned long long int n) { unsigned long long ret = 1,pw = a; while (b!=0) { if (b 1 =
#include<stdio.h>
#include<stdlib.h> #include<time.h> #include<math.h> #define M 12 unsigned long long int Pr(unsigned long long int a,unsigned long long int b,unsigned long long int n) { unsigned long long ret = 1,pw = a; while (b!=0) { if (b & 1 == 1) ret = (ret*pw) % n; pw = (pw*pw) % n; b >>= 1; } return ret; } int Preses(unsigned long long int n) { if (n <= 3) { if (n == 2 || n ==3) return 1; else return 0; } else if (n % 2 == 0 || n%3 == 0) { return 0; } else { time_t ts; unsigned int sum = time(&ts); srand(sum); for (int i = 0;i < M;i++) { unsigned long long int a = (rand() % (n - 2)) + 2; unsigned long long int x = a; unsigned long long int count = 0; unsigned long long int u = n - 1; while (u % 2 == 0) { u = u / 2; } /*while (count < u-1) { x *= a; x %= n; count += count; }*/ x = Pr(a,u,n); while (u < n) { unsigned long long int y = (x * x) % n; if (y == 1 && x != 1 && x != n - 1) { return 0; } x = y; u = u * 2; } if (x != 1) { return 0; } } return 1; } } int main() { int sum = 0; scanf("%d",&sum); unsigned long long int *p = (unsigned long long int *)malloc(sizeof(unsigned long long int) * sum); for (int i = 0; i < sum; i++) { scanf("%lld",&p[i]); } for (int i = 0; i < sum; i++) { int key = Preses(p[i]); if (key == 1) { printf("YESn"); } else { printf("NOn"); } } system("pause"); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |