shunfurh
编程介的小学生
采纳率92.7%
2019-03-18 16:25

素数的队列的计算问题的算法,采用C语言的编程计算实现它

roblem Description
Fermat's theorem states that for any prime number p and for any integer a > 1, a^p == a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)
Given 2 < p ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output
For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Sample Output
no
no
yes
no
yes
yes

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • wudengyu wudengyu 2年前
    #include <stdio.h>
    unsigned long long pow(unsigned long long x, long y,long mod) {
        unsigned long long p = 1;
        while (y) {
            if (y & 1)p = x * p%mod;
            x = x * x%mod;
            y >>= 1;
        }
        return p;
    }
    int prime(long long a) {
        int i;
        if (a == 2)
            return 1;
        for (i = 2; i*i <= a; i++)
            if (a%i == 0)
                return 0;
        return 1;
    }
    void main() {
        long p,a;
        while (1) {
            scanf("%ld %ld", &p, &a);
            if (a == 0 || p == 0)break;
            if (!prime(p)&&pow(a,p,p)==a)
                printf("yes\n");
            else
                printf("no\n");
        }
    }
    
    点赞 评论 复制链接分享

相关推荐