Palindromic primes: Difference between revisions
Content added Content deleted
(Added XPL0 example.) |
(Added Rust solution) |
||
Line 623: | Line 623: | ||
Found 113 palindromic primes that are < 100,000 |
Found 113 palindromic primes that are < 100,000 |
||
done... |
done... |
||
</pre> |
|||
=={{header|Rust}}== |
|||
This includes a solution for the similar task [[Palindromic primes in base 16]]. |
|||
<lang rust>// [dependencies] |
|||
// primal = "0.3" |
|||
// radix_fmt = "1.0" |
|||
fn reverse(base: u64, mut n: u64) -> u64 { |
|||
let mut rev = 0; |
|||
while n > 0 { |
|||
rev = rev * base + n % base; |
|||
n /= base; |
|||
} |
|||
rev |
|||
} |
|||
fn palindromes(base: u64) -> impl std::iter::Iterator<Item = u64> { |
|||
let mut lower = 1; |
|||
let mut upper = base; |
|||
let mut next = 0; |
|||
let mut even = false; |
|||
std::iter::from_fn(move || { |
|||
next += 1; |
|||
if next == upper { |
|||
if even { |
|||
lower = upper; |
|||
upper *= base; |
|||
} |
|||
next = lower; |
|||
even = !even; |
|||
} |
|||
Some(match even { |
|||
true => next * upper + reverse(base, next), |
|||
_ => next * lower + reverse(base, next / base), |
|||
}) |
|||
}) |
|||
} |
|||
fn print_palindromic_primes(base: u64, limit: u64) { |
|||
let width = (limit as f64).log(base as f64).ceil() as usize; |
|||
let mut count = 0; |
|||
let columns = 80 / (width + 1); |
|||
println!("Base {} palindromic primes less than {}:", base, limit); |
|||
for p in palindromes(base) |
|||
.take_while(|x| *x < limit) |
|||
.filter(|x| primal::is_prime(*x)) |
|||
{ |
|||
count += 1; |
|||
print!( |
|||
"{:>w$}", |
|||
radix_fmt::radix(p, base as u8).to_string(), |
|||
w = width |
|||
); |
|||
if count % columns == 0 { |
|||
println!(); |
|||
} else { |
|||
print!(" "); |
|||
} |
|||
} |
|||
if count % columns != 0 { |
|||
println!(); |
|||
} |
|||
println!("Count: {}", count); |
|||
} |
|||
fn count_palindromic_primes(base: u64, limit: u64) { |
|||
let c = palindromes(base) |
|||
.take_while(|x| *x < limit) |
|||
.filter(|x| primal::is_prime(*x)) |
|||
.count(); |
|||
println!( |
|||
"Number of base {} palindromic primes less than {}: {}", |
|||
base, limit, c |
|||
); |
|||
} |
|||
fn main() { |
|||
print_palindromic_primes(10, 1000); |
|||
println!(); |
|||
print_palindromic_primes(10, 100000); |
|||
println!(); |
|||
count_palindromic_primes(10, 1000000000); |
|||
println!(); |
|||
print_palindromic_primes(16, 500); |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Base 10 palindromic primes less than 1000: |
|||
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 |
|||
Count: 20 |
|||
Base 10 palindromic primes less than 100000: |
|||
2 3 5 7 11 101 131 151 181 191 313 353 373 |
|||
383 727 757 787 797 919 929 10301 10501 10601 11311 11411 12421 |
|||
12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661 |
|||
17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013 |
|||
31513 32323 32423 33533 34543 34843 35053 35153 35353 35753 36263 36563 37273 |
|||
37573 38083 38183 38783 39293 70207 70507 70607 71317 71917 72227 72727 73037 |
|||
73237 73637 74047 74747 75557 76367 76667 77377 77477 77977 78487 78787 78887 |
|||
79397 79697 79997 90709 91019 93139 93239 93739 94049 94349 94649 94849 94949 |
|||
95959 96269 96469 96769 97379 97579 97879 98389 98689 |
|||
Count: 113 |
|||
Number of base 10 palindromic primes less than 1000000000: 5953 |
|||
Base 16 palindromic primes less than 500: |
|||
2 3 5 7 b d 11 101 151 161 191 1b1 1c1 |
|||
Count: 13 |
|||
</pre> |
</pre> |
||