Erdös-Selfridge categorization of primes: Difference between revisions
Erdös-Selfridge categorization of primes (view source)
Revision as of 15:28, 22 April 2022
, 2 years agoAdded Rust solution
(Full task) |
(Added Rust solution) |
||
Line 585:
Category 10: first: 1,065,601 last: 15,472,321 count: 28
Category 11: first: 8,524,807 last: 8,524,807 count: 1</pre>
=={{header|Rust}}==
<lang rust>// [dependencies]
// primal = "0.3"
use std::collections::BTreeMap;
struct ErdosSelfridge {
primes: Vec<usize>,
category: Vec<u32>,
}
impl ErdosSelfridge {
fn new(limit: usize) -> ErdosSelfridge {
let mut es = ErdosSelfridge {
primes: Vec::new(),
category: Vec::new(),
};
for prime in primal::Primes::all().take(limit) {
es.primes.push(prime);
}
es.category.resize(es.primes.len(), 0);
es
}
fn get_category(&mut self, index: usize) -> u32 {
if self.category[index] != 0 {
return self.category[index];
}
let mut max_category = 0;
let mut n = self.primes[index] + 1;
for i in 0.. {
let p = self.primes[i];
if p * p > n {
break;
}
let mut count = 0;
while n % p == 0 {
n /= p;
count += 1;
}
if count != 0 {
let category = if p <= 3 { 1 } else { 1 + self.get_category(i) };
max_category = std::cmp::max(max_category, category);
}
}
if n > 1 {
let i = self.get_index(n);
let category = if n <= 3 { 1 } else { 1 + self.get_category(i) };
max_category = std::cmp::max(max_category, category);
}
self.category[index] = max_category;
max_category
}
fn get_index(&self, prime: usize) -> usize {
self.primes.binary_search(&prime).unwrap()
}
fn get_primes_by_category(&mut self, limit: usize) -> BTreeMap<u32, Vec<usize>> {
let mut primes_by_category: BTreeMap<u32, Vec<usize>> = BTreeMap::new();
for i in 0..limit {
let category = self.get_category(i);
let prime = self.primes[i];
if let Some(primes) = primes_by_category.get_mut(&category) {
primes.push(prime);
} else {
let mut primes = Vec::new();
primes.push(prime);
primes_by_category.insert(category, primes);
}
}
primes_by_category
}
}
fn main() {
let mut es = ErdosSelfridge::new(1000000);
let primes_by_category = es.get_primes_by_category(200);
println!("First 200 primes:");
for (category, primes) in primes_by_category.iter() {
println!("Category {}:", category);
for i in 0..primes.len() {
print!(
"{:4}{}",
primes[i],
if (i + 1) % 15 == 0 { "\n" } else { " " }
);
}
print!("\n\n");
}
println!("First 1,000,000 primes:");
let primes_by_category = es.get_primes_by_category(1000000);
for (category, primes) in primes_by_category.iter() {
let first = primes[0];
let count = primes.len();
let last = primes[count - 1];
println!(
"Category {:2}: first = {:7} last = {:8} count = {}",
category, first, last, count
);
}
}</lang>
{{out}}
<pre>
First 200 primes:
Category 1:
2 3 5 7 11 17 23 31 47 53 71 107 127 191 383
431 647 863 971 1151
Category 2:
13 19 29 41 43 59 61 67 79 83 89 97 101 109 131
137 139 149 167 179 197 199 211 223 229 239 241 251 263 269
271 281 283 293 307 317 349 359 367 373 419 433 439 449 461
479 499 503 509 557 563 577 587 593 599 619 641 643 659 709
719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019
1033 1049 1069 1087 1103 1187 1223
Category 3:
37 103 113 151 157 163 173 181 193 227 233 257 277 311 331
337 347 353 379 389 397 401 409 421 457 463 467 487 491 521
523 541 547 569 571 601 607 613 631 653 683 701 727 733 773
787 797 811 821 829 853 857 859 877 883 911 937 947 983 997
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181
1193 1217
Category 4:
73 313 443 617 661 673 677 691 739 757 823 887 907 941 977
1093 1109 1129 1201 1213
Category 5:
1021
First 1,000,000 primes:
Category 1: first = 2 last = 10616831 count = 46
Category 2: first = 13 last = 15482669 count = 10497
Category 3: first = 37 last = 15485863 count = 201987
Category 4: first = 73 last = 15485849 count = 413891
Category 5: first = 1021 last = 15485837 count = 263109
Category 6: first = 2917 last = 15485857 count = 87560
Category 7: first = 15013 last = 15484631 count = 19389
Category 8: first = 49681 last = 15485621 count = 3129
Category 9: first = 532801 last = 15472811 count = 363
Category 10: first = 1065601 last = 15472321 count = 28
Category 11: first = 8524807 last = 8524807 count = 1
</pre>
=={{header|Wren}}==
| |||