Prime triangle: Difference between revisions
Added Rust solution
(Added Go) |
(Added Rust solution) |
||
Line 681:
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448
</pre>
=={{header|Rust}}==
<lang rust>fn is_prime(n: u32) -> bool {
assert!(n < 64);
((1u64 << n) & 0x28208a20a08a28ac) != 0
}
fn prime_triangle(a: &mut [u32]) -> bool {
if a.len() == 2 {
return is_prime(a[0] + a[1]);
}
for i in 1..a.len() - 1 {
if is_prime(a[0] + a[i]) {
a.swap(i, 1);
if prime_triangle(&mut a[1..]) {
return true;
}
a.swap(i, 1);
}
}
false
}
fn prime_triangle_count(a: &mut [u32], count: &mut u32) {
if a.len() == 2 {
if is_prime(a[0] + a[1]) {
*count += 1;
}
return;
}
for i in 1..a.len() - 1 {
if is_prime(a[0] + a[i]) {
a.swap(i, 1);
prime_triangle_count(&mut a[1..], count);
a.swap(i, 1);
}
}
}
fn print(a: &[u32]) {
if a.is_empty() {
return;
}
print!("{:2}", a[0]);
for x in &a[1..] {
print!(" {:2}", x);
}
println!();
}
fn main() {
use std::time::Instant;
let start = Instant::now();
for n in 2..21 {
let mut a: Vec<u32> = (1..=n).collect();
if prime_triangle(&mut a) {
print(&a);
}
}
println!();
for n in 2..21 {
let mut a: Vec<u32> = (1..=n).collect();
let mut count = 0;
prime_triangle_count(&mut a, &mut count);
if n == 2 {
print!("{count}");
} else {
print!(" {count}");
}
}
println!();
let time = start.elapsed();
println!("\nElapsed time: {} milliseconds", time.as_millis());
}</lang>
{{out}}
<pre>
1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 4 3 2 5 6 7
1 2 3 4 7 6 5 8
1 2 3 4 7 6 5 8 9
1 2 3 4 7 6 5 8 9 10
1 2 3 4 7 10 9 8 5 6 11
1 2 3 4 7 10 9 8 5 6 11 12
1 2 3 4 7 6 5 12 11 8 9 10 13
1 2 3 4 7 6 13 10 9 8 11 12 5 14
1 2 3 4 7 6 13 10 9 8 11 12 5 14 15
1 2 3 4 7 6 5 12 11 8 15 14 9 10 13 16
1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14 17
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
Elapsed time: 754 milliseconds
</pre>
| |||