Prime triangle: Difference between revisions
Content added Content deleted
(Added Go) |
(Added Rust solution) |
||
Line 681: | Line 681: | ||
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 |
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> |
</pre> |
||