Skip to content

Instantly share code, notes, and snippets.

@tasuten
Last active January 1, 2017 13:34
Show Gist options
  • Save tasuten/e6bd03d85acf5846157c59d44b9a818c to your computer and use it in GitHub Desktop.
Save tasuten/e6bd03d85acf5846157c59d44b9a818c to your computer and use it in GitHub Desktop.
書き初め@2017
fn is_prime(n: u64) -> bool {
return miller_rabin_test(n,
[2, 325, 9375, 28178, 450775, 9780504, 1795265022]);
}
fn miller_rabin_test(n: u64, bases: [u64; 7]) -> bool {
match n {
0 | 1 => return false,
2 | 3 => return true,
n if n & 1 == 0 => return false,
n => {
let mut d = n-1;
while d & 1 == 0 {
d >>= 1 ;
}
for base in bases.iter() {
let mut t = d;
let mut y = mod_pow(*base, t, n);
while t != n-1 && y != 1 && y != n-1 {
y = ( y * y ) % n;
t <<= 1;
}
if y != n-1 && t & 1 == 0 {
return false ;
}
}
return true;
}
}
}
fn mod_pow(base: u64, pow: u64, modulo: u64) -> u64{
let mut result = 1;
let mut b = base;
let mut p = pow;
while p > 0 {
if p & 1 == 1 {
result = ( result * b ) % modulo;
}
b = (b * b) % modulo;
p >>= 1;
}
return result;
}
fn main() {
let new_year = 2017;
if is_prime(new_year) {
println!("{} is prime year!", new_year);
} else {
println!("{} is not prime year...", new_year);
}
}
@tasuten
Copy link
Author

tasuten commented Jan 1, 2017

2017 is prime year!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment