fork download
copy 
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5.  
  6. int power(int a, int b, int c) {
  7.     int result = 1;
  8.     a = a % c;
  9.  
  10.     while (b > 0) {
  11.         if (b%2==1)
  12.             result = (result * a) % c;
  13.         b/=2;
  14.         a = (a * a) % c;
  15.     }
  16.  
  17.     return result;
  18. }
  19.  
  20. bool is_prime(int n, int k) {
  21.     if (n <= 1 || n == 4)
  22.         return false;
  23.     else if (n <= 3)
  24.         return true;
  25.  
  26.     int s = 0, d = n - 1;
  27.     while (d % 2 == 0) {
  28.         s++;
  29.         d /= 2;
  30.     }
  31.  
  32.     for (int i = 0; i < k; i++) {
  33.         int a = rand() % (n - 3) + 2;
  34.         int x = power(a, d, n);
  35.  
  36.         if (x == 1 || x == n - 1)
  37.             continue;
  38.  
  39.         for (int j = 1; j < s; j++) {
  40.             x = power(x, 2, n);
  41.             if (x == 1)
  42.                 return false;
  43.             else if (x == n - 1)
  44.                 break;
  45.         }
  46.  
  47.         if (x != n - 1)
  48.             return false;
  49.     }
  50.  
  51.     return true;
  52. }
  53.  
  54. int main() {
  55.     int n, k;
  56.     printf("Nhap mot so nguyen duong: ");
  57.     scanf("%d", &n);
  58.     printf("Nhap so lan kiem tra (k): ");
  59.     scanf("%d", &k);
  60.  
  61.     if (is_prime(n, k))
  62.         printf("%d la so nguyen to.\n", n);
  63.     else
  64.         printf("%d la hop so.\n", n);
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Nhap mot so nguyen duong: Nhap so lan kiem tra (k): 887772416 la hop so.
https://ideone.com/FnNsoS
language:
C (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!