use std::collections::HashMap;
use std::fs::File;
use std::io::{BufWriter, Write};
use std::sync::{Arc, Mutex};
use std::time::Instant;
type PrimeType = u64;
// Быстрое решето Эратосфена для нахождения всех простых чисел
fn segmented_sieve_fast(limit: usize) -> Vec<PrimeType> {
let start_time = Instant::now();
println!("Генерация простых чисел до {}...", limit);
if limit < 2 {
return Vec::new();
}
let segment_size = 1_000_000;
let sqrt_limit = (limit as f64).sqrt() as usize;
// Сначала находим простые до sqrt(limit) классическим решетом
let mut is_prime_small = vec![true; sqrt_limit + 1];
is_prime_small[0] = false;
is_prime_small[1] = false;
for i in 2..=sqrt_limit {
if is_prime_small[i] {
let mut j = i * i;
while j <= sqrt_limit {
is_prime_small[j] = false;
j += i;
}
}
}
let small_primes: Vec<usize> = is_prime_small
.iter()
.enumerate()
.filter(|(_, &is_prime)| is_prime)
.map(|(i, _)| i)
.collect();
let mut primes = Vec::with_capacity(limit / (limit as f64).ln() as usize);
primes.extend(small_primes.iter().map(|&p| p as PrimeType));
// Сегментированное решето
let num_segments = (limit - sqrt_limit + segment_size - 1) / segment_size;
for seg in 0..num_segments {
let low = sqrt_limit + 1 + seg * segment_size;
let high = std::cmp::min(low + segment_size - 1, limit);
let size = high - low + 1;
let mut sieve = vec![true; size];
for &p in &small_primes {
if p * p > high {
break;
}
let start = std::cmp::max(p * p, ((low + p - 1) / p) * p);
if start > high {
continue;
}
let start_idx = start - low;
for j in (start_idx..size).step_by(p) {
sieve[j] = false;
}
}
for (i, &is_prime) in sieve.iter().enumerate() {
if is_prime {
primes.push((low + i) as PrimeType);
}
}
if seg % 100 == 0 && seg > 0 {
println!(" Сегмент {}/{} обработан", seg, num_segments);
}
}
println!("Найдено {} простых чисел за {:?}", primes.len(), start_time.elapsed());
primes
}
// Быстрая проверка простоты
fn is_prime_fast(n: PrimeType, small_primes: &[usize], prime_cache: &[bool]) -> bool {
if n <= 1 {
return false;
}
if n == 2 || n == 3 {
return true;
}
if n % 2 == 0 || n % 3 == 0 {
return false;
}
let n_usize = n as usize;
// Если число в пределах кэша, используем кэш
if n_usize < prime_cache.len() {
return prime_cache[n_usize];
}
// Проверяем делимость на маленькие простые числа
for &p in small_primes {
if p * p > n_usize {
break;
}
if n_usize % p == 0 {
return false;
}
}
// Проверяем делимость на числа вида 6k ± 1
let mut i = 5;
while i * i <= n_usize {
if n_usize % i == 0 || n_usize % (i + 2) == 0 {
return false;
}
i += 6;
}
true
}
// Простое решето для создания булевого массива
fn simple_sieve_to_bool(limit: usize) -> Vec<bool> {
if limit < 2 {
return vec![false; limit + 1];
}
let mut is_prime = vec![true; limit + 1];
is_prime[0] = false;
is_prime[1] = false;
let sqrt_limit = (limit as f64).sqrt() as usize;
for i in 2..=sqrt_limit {
if is_prime[i] {
let mut j = i * i;
while j <= limit {
is_prime[j] = false;
j += i;
}
}
}
is_prime
}
// Главная функция поиска
fn find_primes_with_many_representations(
limit: PrimeType,
min_representations: usize,
num_threads: usize,
) -> Vec<(PrimeType, Vec<(PrimeType, PrimeType, usize)>)> {
let total_start = Instant::now();
// Генерируем простые числа
let primes_start = Instant::now();
let primes = segmented_sieve_fast(limit as usize);
println!("Простые числа сгенерированы за {:?}", primes_start.elapsed());
// Создаем префиксные суммы
println!("Создание префиксных сумм...");
let prefix_start = Instant::now();
let mut prefix_sums = vec![0u64; primes.len() + 1];
for i in 0..primes.len() {
prefix_sums[i + 1] = prefix_sums[i] + primes[i];
}
println!("Префиксные суммы созданы за {:?}", prefix_start.elapsed());
// Кэш простых чисел для быстрой проверки
println!("Создание кэша простых чисел...");
let cache_limit = 10_000_000; // 10 миллионов для кэша
let prime_cache = simple_sieve_to_bool(cache_limit);
let small_primes_for_check: Vec<usize> = prime_cache
.iter()
.enumerate()
.filter(|(_, &is_prime)| is_prime)
.map(|(i, _)| i)
.collect();
// Подготовка для многопоточности
println!("Подготовка многопоточного поиска с {} потоками...", num_threads);
let primes_arc = Arc::new(primes);
let prefix_sums_arc = Arc::new(prefix_sums);
let result_map = Arc::new(Mutex::new(HashMap::new()));
// Ручное разделение работы на потоки
let chunk_size = primes_arc.len() / num_threads;
let mut handles = Vec::new();
println!("Начинаем поиск представлений...");
let search_start = Instant::now();
for thread_id in 0..num_threads {
let primes_clone = Arc::clone(&primes_arc);
let prefix_sums_clone = Arc::clone(&prefix_sums_arc);
let result_map_clone = Arc::clone(&result_map);
let small_primes_clone = small_primes_for_check.clone();
let prime_cache_clone = prime_cache.clone();
let start_idx = thread_id * chunk_size;
let end_idx = if thread_id == num_threads - 1 {
primes_clone.len()
} else {
(thread_id + 1) * chunk_size
};
let handle = std::thread::spawn(move || {
let mut local_map = HashMap::new();
for i in start_idx..end_idx {
let start_prime = primes_clone[i];
// Оптимизированный поиск с использованием префиксных сумм
let mut j = i;
while j < primes_clone.len() {
let sum = prefix_sums_clone[j + 1] - prefix_sums_clone[i];
if sum > limit {
break;
}
// Проверяем, является ли сумма простым числом
if sum >= 2 {
let length = j - i + 1;
if length >= 3 && is_prime_fast(sum, &small_primes_clone, &prime_cache_clone) {
let representation = (start_prime, primes_clone[j], length);
local_map.entry(sum)
.or_insert_with(Vec::new)
.push(representation);
}
}
j += 1;
}
// Прогресс
if thread_id == 0 && i % 10000 == 0 {
let processed = i - start_idx;
let total = end_idx - start_idx;
print!("\rПоток 0: {}/{} ({:.1}%)",
processed, total,
(processed as f64 / total as f64) * 100.0);
std::io::Write::flush(&mut std::io::stdout()).unwrap();
}
}
// Добавляем результаты в общую мапу
let mut global_map = result_map_clone.lock().unwrap();
for (prime, representations) in local_map {
global_map.entry(prime)
.or_insert_with(Vec::new)
.extend(representations);
}
});
handles.push(handle);
}
// Ждем завершения всех потоков
for handle in handles {
handle.join().unwrap();
}
println!("\nПоиск завершен за {:?}", search_start.elapsed());
// Собираем результаты
let result_map = Arc::try_unwrap(result_map).unwrap().into_inner().unwrap();
println!("Всего найдено {} чисел с представлениями", result_map.len());
let mut results = Vec::new();
for (prime, representations) in result_map {
if representations.len() >= min_representations {
results.push((prime, representations));
}
}
// Сортируем по количеству представлений (по убыванию)
results.sort_by(|a, b| b.1.len().cmp(&a.1.len()));
println!("Найдено {} чисел с {} и более представлениями",
results.len(), min_representations);
println!("Общее время выполнения: {:?}", total_start.elapsed());
results
}
// Функция для сохранения результатов
fn save_results_to_file(
results: &[(PrimeType, Vec<(PrimeType, PrimeType, usize)>)],
filename: &str,
) -> std::io::Result<()> {
println!("Сохранение результатов в файл {}...", filename);
let file = File::create(filename)?;
let mut writer = BufWriter::new(file);
writeln!(writer, "Простые числа до 1 миллиарда, представимые суммой последовательных простых чисел")?;
writeln!(writer, "Минимальное количество представлений: 8")?;
writeln!(writer, "{}", "=".repeat(80))?;
writeln!(writer)?;
for (prime_idx, (prime, representations)) in results.iter().enumerate() {
writeln!(writer, "{}. Простое число: {}", prime_idx + 1, prime)?;
writeln!(writer, " Количество представлений: {}", representations.len())?;
// Сортируем представления по длине последовательности
let mut sorted_reps = representations.clone();
sorted_reps.sort_by(|a, b| b.2.cmp(&a.2));
let show_count = std::cmp::min(10, sorted_reps.len());
for i in 0..show_count {
let (start, end, length) = sorted_reps[i];
writeln!(writer, " {}. {} = {} + ... + {} ({} чисел)",
i + 1, prime, start, end, length)?;
}
if sorted_reps.len() > 10 {
writeln!(writer, " ... и еще {} представлений", sorted_reps.len() - 10)?;
}
// Вычисляем минимальную и максимальную длину последовательности
let min_len = representations.iter().map(|&(_, _, len)| len).min().unwrap_or(0);
let max_len = representations.iter().map(|&(_, _, len)| len).max().unwrap_or(0);
writeln!(writer, " Диапазон длин: от {} до {} чисел", min_len, max_len)?;
writeln!(writer)?;
}
// Сводная статистика
writeln!(writer, "{}", "=".repeat(80))?;
writeln!(writer, "СВОДНАЯ СТАТИСТИКА:")?;
writeln!(writer)?;
let total_numbers = results.len();
let max_representations = results.iter()
.map(|(_, reps)| reps.len())
.max()
.unwrap_or(0);
writeln!(writer, "Всего найдено чисел: {}", total_numbers)?;
writeln!(writer, "Максимальное количество представлений: {}", max_representations)?;
// Распределение по количеству представлений
let mut distribution = HashMap::new();
for (_, reps) in results {
*distribution.entry(reps.len()).or_insert(0) += 1;
}
let mut dist_vec: Vec<_> = distribution.iter().collect();
dist_vec.sort_by(|a, b| b.0.cmp(a.0));
writeln!(writer, "\nРаспределение по количеству представлений:")?;
for (&count, &num) in dist_vec {
writeln!(writer, " {} представлений: {} чисел", count, num)?;
}
println!("Результаты сохранены в файл: {}", filename);
Ok(())
}
pub fn main_atpn() {
println!("ПОИСК ПРОСТЫХ ЧИСЕЛ ДО 1 МИЛЛИАРДА");
println!("Ищем числа, представимые суммой последовательных простых чисел");
println!("Минимальная длина последовательности: 3 числа");
println!("Минимальное количество представлений: 8");
println!("{}", "=".repeat(80));
let limit: PrimeType = 1_000_000_000;
let min_representations = 8;
let num_threads = num_cpus::get();
println!("Используется {} потоков", num_threads);
println!("Начинаем поиск...\n");
let results = find_primes_with_many_representations(limit, min_representations, num_threads);
if results.is_empty() {
println!("Не найдено чисел с {} и более представлениями", min_representations);
return;
}
// Выводим краткую статистику
println!("\n{}", "=".repeat(80));
println!("РЕЗУЛЬТАТЫ:");
println!("Найдено {} чисел с {} и более представлениями", results.len(), min_representations);
// Топ-10 чисел с максимальным количеством представлений
println!("\nТоп-10 чисел с наибольшим количеством представлений:");
for (i, (prime, representations)) in results.iter().take(10).enumerate() {
println!("{}. {} ({} представлений)", i + 1, prime, representations.len());
}
// Сохраняем все результаты в файл
let filename = "primes_with_many_representations.txt";
if let Err(e) = save_results_to_file(&results, filename) {
println!("Ошибка при сохранении в файл: {}", e);
}
// Дополнительно сохраняем числа с 10+ представлениями в отдельный файл
let high_results: Vec<_> = results.iter()
.filter(|(_, reps)| reps.len() >= 10)
.cloned()
.collect();
if !high_results.is_empty() {
let high_filename = "primes_with_10plus_representations.txt";
if let Err(e) = save_results_to_file(&high_results, high_filename) {
println!("Ошибка при сохранении файла с 10+ представлениями: {}", e);
}
}
// Пример детального вывода для первого числа
if let Some((first_prime, first_reps)) = results.first() {
println!("\n{}", "=".repeat(80));
println!("ПОДРОБНЫЙ ПРИМЕР ДЛЯ ПЕРВОГО ЧИСЛА:");
println!("Число {} ({} представлений):", first_prime, first_reps.len());
let mut sorted_reps = first_reps.clone();
sorted_reps.sort_by(|a, b| b.2.cmp(&a.2));
for (i, (start, end, length)) in sorted_reps.iter().take(5).enumerate() {
println!(" {}. От {} до {} ({} чисел)", i + 1, start, end, length);
}
if first_reps.len() > 5 {
println!(" ... и еще {} представлений", first_reps.len() - 5);
}
}
}
29.01.2026, 15:36 
