/* Primality test. | |
* | |
* Copyright (C) 2013 Chen-Pang He <jdh8@ms63.hinet.net> | |
* Don’t copy-paste the email. It won’t work. | |
* | |
* This program is free software: you can redistribute it and/or modify | |
* it under the terms of the GNU General Public License as published by | |
* the Free Software Foundation, either version 3 of the License, or | |
* (at your option) any later version. | |
* | |
* This program is distributed in the hope that it will be useful, | |
* but WITHOUT ANY WARRANTY; without even the implied warranty of | |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
* GNU General Public License for more details. | |
* | |
* You should have received a copy of the GNU General Public License | |
* along with this program. If not, see <http://www.gnu.org/licenses/>. | |
*/ | |
#include <limits.h> | |
#include <stdint.h> | |
#include <stdio.h> | |
#include <stdlib.h> | |
uint32_t powmod (uint32_t base, uint32_t exp, uint32_t mod) | |
{ | |
uint32_t res = 1; | |
base %= mod; | |
while (exp) { | |
if (exp % 2) | |
res = res * (uint64_t)base % mod; | |
exp /= 2; | |
base = base * (uint64_t)base % mod; | |
} | |
return res; | |
} | |
/* Deterministic Miller-Rabin primality test */ | |
int isPrime (uint32_t n) | |
{ | |
uint32_t d, r, s; | |
switch (n) { | |
case 0: | |
case 1: | |
return 0; | |
case 2: | |
return 1; | |
} | |
d = n - 1; | |
s = 0; | |
while (d % 2 == 0) { | |
d /= 2; | |
++s; | |
} | |
for (r=0; r<s; ++r) { | |
if (powmod(2, d, n) == 1 || powmod(2, d << r, n) == n - 1 || | |
powmod(7, d, n) == 1 || powmod(7, d << r, n) == n - 1 || | |
powmod(61, d, n) == 1 || powmod(61, d << r, n) == n - 1) | |
return 1; | |
} | |
return 0; | |
} | |
int main (int argc, char *argv[]) | |
{ | |
uint32_t n; | |
if (argc != 2) { | |
printf("Usage: %s num\n", argv[0]); | |
puts("Test if num is prime.\n" | |
"Warning: This program may crash if num overflows uint32_t."); | |
return 1; | |
} | |
n = strtoul(argv[1], NULL, 10); | |
if (isPrime(n)) | |
printf("%u is prime.\n", n); | |
else | |
printf("%u is composite.\n", n); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment