4
\$\begingroup\$

Problem: https://projecteuler.net/problem=51

"Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family."

repository: https://github.com/steven-omaha/euler51

dependencies: num

This code is my attempt at solving Project Euler challenge #51. This code takes ~ 1000 ms to run on my PC.

Comments from me:

  • primes.rs is intentionally generic, as most a good amount of Project Euler challenges involve prime numbers. This is normally a separate package.
  • combination.rs produces Vec<bool> elements, like [1, 0, 0, 1, 1]. These vectors are used in main.rs to identify the positions where a digit should be replaced.

Main concerns for review:

  • Single-thread performance. I am aware of multithreading, but I'm not interested in that in the scope of this review. Am I giving away performance improvements somewhere?
  • code cleanliness
  • any code smells

Things that I'm aware are suboptimal:

  • apply_transformation does too much and would better be two functions (see comments there). I was thinking on how to transfer the data between the (hypothetical) two different functions. I tried that by collecting to a Vec, but that had some performance penalty. I think the best would be to implement Map, but I have never done that.
  • I have a feeling that transforming an int to an array of digits via char is suboptimal, but I have not measured that.

main.rs:

mod combination;
mod primes;

use combination::PositionCombinations;
use primes::Primes;

type Int = u64;

// EXAMPLE 1
// const MIN_VALUE: Int = 10;
// const MAX_VALUE: Int = 99;
// const LENGTH: usize = 2;
// const MIN_LENGTH: usize = 1;

// EXAMPLE 2
// const MIN_VALUE: Int = 10_000;
// const MAX_VALUE: Int = 99_999;
// const LENGTH: usize = 5;
// const MIN_LENGTH: usize = 2;

// FINAL
const MIN_VALUE: Int = 100_000;
const MAX_VALUE: Int = 999_999;
const LENGTH: usize = 6;
const MIN_LENGTH: usize = 2;

const MAX_LENGTH: usize = LENGTH - 1;
const DIGITS: [u8; 10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

fn main() {
    let all_primes = Primes::get_between(MIN_VALUE, MAX_VALUE);
    let mut best_of_all_combinations = vec![];
    for pattern in PositionCombinations::new(MIN_LENGTH, MAX_LENGTH, LENGTH) {
        let mut best_this_combination = vec![];
        let mut primes_to_check = all_primes.clone();
        while let Some(first) = primes_to_check.pop() {
            let mut primes_matching_pattern = vec![];
            let digits = first.to_digits();
            for digit in DIGITS {
                let could_be_prime = apply_transformation(&digits, digit, &pattern);
                if primes_to_check.contains(&could_be_prime) || could_be_prime == first {
                    primes_matching_pattern.push(could_be_prime);
                }
            }
            if primes_matching_pattern.len() > 2 {
                best_this_combination.push(primes_matching_pattern);
            }
        }
        if !best_this_combination.is_empty() {
            best_of_all_combinations.push(get_longest(best_this_combination));
        }
    }
    println!("{:#?}", get_longest(best_of_all_combinations));
}

fn apply_transformation(prime_as_digits: &[u8], new_digit: u8, pattern: &[bool]) -> Int {
    debug_assert_eq!(prime_as_digits.len(), pattern.len());
    let mut multiplier = 1;
    let result = prime_as_digits
        // apply the pattern to prime_as_digits
        .iter()
        .zip(pattern)
        .map(|(old_digit, replace)| if *replace { new_digit } else { *old_digit })
        .map(Int::from)
        // calculate Int
        .rev()
        .reduce(|accum, item| {
            multiplier *= 10;
            accum + multiplier * item
        })
        .unwrap();
    debug_assert_eq!(multiplier, 100_000);
    result
}

fn get_longest(mut vec: Vec<Vec<Int>>) -> Vec<Int> {
    assert!(
        !vec.is_empty(),
        "cannot get the longest element of an empty vector"
    );
    vec.sort_by_key(Vec::len);
    let length = vec.last().unwrap().len();
    vec.into_iter().find(|v| v.len() == length).unwrap()
}

trait ToDigits {
    fn to_digits(&self) -> Vec<u8>;
}

impl ToDigits for Int {
    fn to_digits(&self) -> Vec<u8> {
        self.to_string()
            .chars()
            .map(|x| x.to_digit(10).unwrap() as u8)
            .collect()
    }
}

#[cfg(test)]
mod test {
    use crate::{apply_transformation, ToDigits};

    #[test]
    fn test_num_to_digits() {
        let num = 83371;
        assert_eq!(num.to_digits(), vec![8, 3, 3, 7, 1]);
    }

    #[test]
    fn test_apply_transformation() {
        let prime_as_digits = [5, 7, 3, 8, 2, 1];
        let new_digit = 0;
        let pattern = [false, true, true, true, false, false];
        assert_eq!(
            apply_transformation(&prime_as_digits, new_digit, &pattern),
            500_021
        );
    }
}

combination.rs:

pub struct PositionCombinations {
    min_length: usize,
    max_length: usize,
    state: Vec<bool>,
    finished: bool,
}

impl Iterator for PositionCombinations {
    type Item = Vec<bool>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let result = self.state.clone();
            self.increment();
            if self.finished {
                return None;
            }
            if (self.min_length..=self.max_length).contains(&result.iter().filter(|x| **x).count())
            {
                return Some(result);
            }
        }
    }
}

impl PositionCombinations {
    pub fn new(min_length: usize, max_length: usize, length: usize) -> Self {
        let state = vec![false; length];
        let finished = false;
        Self {
            min_length,
            max_length,
            state,
            finished,
        }
    }

    fn increment(&mut self) {
        let mut overflow = self.state[0];
        self.state[0] ^= true;
        for position in self.state[1..].iter_mut() {
            let new_overflow = *position & overflow;
            *position ^= overflow;
            overflow = new_overflow;
        }
        if overflow {
            self.finished = true;
        }
    }
}

pub trait ToString {
    fn to_string(&self) -> String;
}

impl ToString for Vec<bool> {
    fn to_string(&self) -> String {
        self.iter().map(|b| if *b { 'x' } else { '.' }).collect()
    }
}

#[cfg(test)]
mod test {
    use crate::combination::PositionCombinations;
    use std::collections::HashSet;

    #[test]
    fn test_combination_2_3_4() {
        let combinator = PositionCombinations::new(2, 3, 4);
        let result: Vec<_> = combinator.into_iter().collect();
        let mut number_solutions = result.len();
        let mut solution = HashSet::new();
        solution.insert(vec![false, false, true, true]);
        solution.insert(vec![false, true, false, true]);
        solution.insert(vec![false, true, true, false]);
        solution.insert(vec![false, true, true, true]);
        solution.insert(vec![true, true, false, false]);
        solution.insert(vec![true, false, true, false]);
        solution.insert(vec![true, false, false, true]);
        solution.insert(vec![true, false, true, true]);
        solution.insert(vec![true, true, false, true]);
        solution.insert(vec![true, true, true, false]);
        for item in solution {
            assert!(result.contains(&item));
            number_solutions -= 1;
        }
        assert_eq!(number_solutions, 0);
    }

    #[test]
    fn test_combination_2_2_3() {
        let combinator = PositionCombinations::new(2, 2, 3);
        let result: Vec<_> = combinator.into_iter().collect();
        let mut number_solutions = result.len();
        let mut solution = HashSet::new();
        solution.insert(vec![false, true, true]);
        solution.insert(vec![true, false, true]);
        solution.insert(vec![true, true, false]);
        for item in solution {
            assert!(result.contains(&item));
            number_solutions -= 1;
        }
        assert_eq!(number_solutions, 0);
    }
}

primes.rs

extern crate num;

use num::FromPrimitive;
use num::Num;
use num::ToPrimitive;
use std::collections::HashSet;
use std::hash::Hash;

#[derive(Clone)]
pub struct Primes<T> {
    vector: Vec<T>,
    set: HashSet<T>,
}

impl<T> Primes<T>
where
    T: Num + ToPrimitive + FromPrimitive + Hash + Eq + PartialEq + Copy,
{
    pub fn get_between(min_value: T, max_value: T) -> Self {
        let max_value = max_value.to_usize().unwrap();
        let min_value = min_value.to_usize().unwrap();
        assert!(min_value > 1);
        assert!(max_value > min_value);
        Self::from_array(
            &Self::get_prime_numbers_array(min_value, max_value),
            min_value,
            max_value,
        )
    }

    fn from_array(array: &[bool], min_value: usize, max_value: usize) -> Self {
        let mut vector = Vec::new();
        let mut set = HashSet::new();
        for number in min_value..max_value {
            if array[(number - min_value) as usize] {
                let prime = FromPrimitive::from_usize(number).unwrap();
                vector.push(prime);
                set.insert(prime);
            }
        }
        vector.reverse(); // so that self.pop removes the smallest prime
        Primes { vector, set }
    }

    fn get_prime_numbers_array(min_value: usize, max_value: usize) -> Vec<bool> {
        // Sieve of Eratosthenes
        let length = max_value - min_value;
        let mut result = vec![true; length];

        for number_to_check in 2..(max_value / 2) {
            let mut last_number = number_to_check;
            loop {
                let current_number = last_number + number_to_check;
                if current_number < min_value {
                    last_number = current_number;
                    continue;
                }
                if current_number >= max_value {
                    break;
                }
                result[current_number - min_value] = false;
                last_number = current_number;
            }
        }
        result
    }

    pub fn pop(&mut self) -> Option<T> {
        let result = self.vector.pop();
        if let Some(value) = result {
            self.set.remove(&value);
        }
        result
    }

    pub fn contains(&self, val: &T) -> bool {
        self.set.contains(val)
    }
}

#[cfg(test)]
mod test {
    use crate::primes::Primes;

    #[test]
    fn test_example_prime() {
        let primes = Primes::get_between(2, 99_999);
        assert!(primes.set.contains(&56003));
        assert!(primes.set.contains(&56993));
        assert!(!primes.set.contains(&56002));
    }

    #[test]
    fn test_pop() {
        let mut primes = Primes::get_between(10, 20);
        assert!(primes.contains(&11));
        primes.pop();
        assert!(!primes.contains(&11));
    }
}

Thank you for your time!

\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

Using the comments and the other answer, I have attempted to rework this code myself.

  • Runtime is down from 1000 ms to 100 ms.
  • My implementation of the sieve of Eratosthenes was indeed weird and needlessly complicated, although correct. I have rewritten that and thrown some optimizations on it (benchmarked, of course).
  • apply_transformation was a bad name that I should have replaced before asking for a review. It is now called replace_digits_with_new_digit_according_to_pattern
  • I had best_this_combination and bets_of_all_combinations where I held the longest prime family fulfilling the conditions that I have found so far, instead of just checking whether I found the family of the correct size and exiting the program.
  • My old variant of ToDigits was indeed suboptimal performance-wise (Int to String to char to u8). It now converts the number directly to Vec<u8> using some basic multiplication and subtraction.
  • I had the correct idea that I do not need to check numbers again that I had already checked, but I did it in an inefficient manner. I cloned the original all_primes struct for every outer iteration, and popped one prime out of it for every inner iteration. The comments were helpful insofar that I realized I can have a case string to check if I had checked that combination of digits before. (get_case_string).
  • Furthermore, I found that I could get out of the inner loop earlier when there are not enough digits left so that I can find a family of the required size. (enough_digits_left)
  • The case strings and processed cases are written to a pre-allocated buffer, which prevents a lot of allocations and drops in the main loop.

This is how the code looks like now.

Repository is updated. https://github.com/steven-omaha/euler51

main.rs

mod combination;
mod primes;

use std::{collections::HashSet, process::exit};

use combination::PositionCombinations;
use primes::Primes;

type Int = u64;

// EXAMPLE 1
// const SEARCH_MIN: Int = 10;
// const SEARCH_MAX: Int = 99;
// const AMOUNT_OF_DIGITS_IN_NUMBER: usize = 2;
// const MIN_PATTERN_LENGTH: usize = 1;
// const FAMILY_SIZE: usize = 6;

// EXAMPLE 2
// const SEARCH_MIN: Int = 10_000;
// const SEARCH_MAX: Int = 99_999;
// const AMOUNT_OF_DIGITS_IN_NUMBER: usize = 5;
// const MIN_PATTERN_LENGTH: usize = 1;
// const FAMILY_SIZE: usize = 7;

// FINAL
const SEARCH_MIN: Int = 100_000;
const SEARCH_MAX: Int = 999_999;
const AMOUNT_OF_DIGITS_IN_NUMBER: usize = 6;
const MIN_PATTERN_LENGTH: usize = 2;
const FAMILY_SIZE: usize = 8;

const MAX_PATTERN_LENGTH: usize = AMOUNT_OF_DIGITS_IN_NUMBER - 1;
const NUMBER_OF_DIGITS: usize = 10;
const DIGITS: [u8; NUMBER_OF_DIGITS] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

fn main() {
    let all_primes = Primes::get_between(SEARCH_MIN, SEARCH_MAX);
    let mut processed_cases = HashSet::with_capacity(SEARCH_MIN as usize);
    let mut primes_matching_pattern = Vec::with_capacity(FAMILY_SIZE);
    let mut case_buf = String::with_capacity(AMOUNT_OF_DIGITS_IN_NUMBER);

    for pattern in PositionCombinations::new(
        MIN_PATTERN_LENGTH,
        MAX_PATTERN_LENGTH,
        AMOUNT_OF_DIGITS_IN_NUMBER,
    ) {
        for prime in &all_primes.vector {
            primes_matching_pattern.clear();

            let digits = prime.to_digits();

            get_case_string(&digits, &pattern, &mut case_buf);
            if processed_cases.contains(&case_buf) {
                continue;
            } else {
                processed_cases.insert(case_buf.clone());
            }

            for (i, digit) in DIGITS.iter().enumerate() {
                if !enough_digits_left(i, primes_matching_pattern.len()) {
                    break;
                }
                let could_be_prime =
                    replace_digits_with_new_digit_according_to_pattern(&digits, *digit, &pattern);
                if all_primes.contains(&could_be_prime) {
                    primes_matching_pattern.push(could_be_prime);
                }
            }
            if primes_matching_pattern.len() == FAMILY_SIZE {
                println!("{primes_matching_pattern:#?}");
                exit(0);
            }
        }
    }
}

fn enough_digits_left(i: usize, primes_len: usize) -> bool {
    // are there enough digits left in the loop to achieve the required FAMILY_SIZE?
    i - primes_len + FAMILY_SIZE <= NUMBER_OF_DIGITS
}

fn get_case_string(digits: &[u8], pattern: &[bool], buf: &mut String) {
    buf.clear();
    digits
        .iter()
        .zip(pattern)
        .map(|(d, b)| if *b { '*' } else { *d as char })
        .for_each(|c| buf.push(c));
}

fn replace_digits_with_new_digit_according_to_pattern(
    prime_as_digits: &[u8],
    new_digit: u8,
    pattern: &[bool],
) -> Int {
    debug_assert_eq!(prime_as_digits.len(), pattern.len());
    let mut multiplier = 1;
    let result = prime_as_digits
        // apply the pattern to prime_as_digits
        .iter()
        .zip(pattern)
        .map(|(old_digit, replace)| if *replace { new_digit } else { *old_digit })
        .map(|d| d as Int)
        // calculate Int
        .rev()
        .reduce(|accum, item| {
            multiplier *= 10;
            accum + multiplier * item
        })
        .unwrap();
    debug_assert_eq!(multiplier, 100_000);
    result
}

trait ToDigits {
    fn to_digits(&self) -> Vec<u8>;
}

impl ToDigits for Int {
    fn to_digits(&self) -> Vec<u8> {
        let oom = get_order_of_magnitude(*self);
        let length = oom as usize;
        let mut var = *self;
        let mut result = vec![0; length];

        result.iter_mut().enumerate().for_each(|(i, d)| {
            let power = 10_u64.pow(oom - i as u32 - 1);
            let digit = var / power;
            var -= digit * power;
            *d = digit as u8;
        });

        debug_assert_eq!(var, 0);
        result
    }
}

fn get_order_of_magnitude(x: Int) -> u32 {
    let mut tmp = 1;
    let mut oom = 1;
    while tmp - 1 < x {
        oom += 1;
        tmp *= 10;
    }
    oom - 1
}

#[cfg(test)]
mod test {
    use crate::{
        get_order_of_magnitude, replace_digits_with_new_digit_according_to_pattern, ToDigits,
    };

    #[test]
    fn test_num_to_digits() {
        let num = 83371;
        assert_eq!(num.to_digits(), vec![8, 3, 3, 7, 1]);
    }

    #[test]
    fn test_apply_transformation() {
        let prime_as_digits = [5, 7, 3, 8, 2, 1];
        let new_digit = 0;
        let pattern = [false, true, true, true, false, false];
        assert_eq!(
            replace_digits_with_new_digit_according_to_pattern(
                &prime_as_digits,
                new_digit,
                &pattern
            ),
            500_021
        );
    }

    #[test]
    fn test_to_digits() {
        let num = 37871_u64;
        assert_eq!(vec![3, 7, 8, 7, 1], num.to_digits());
    }

    #[test]
    fn test_oom() {
        assert_eq!(get_order_of_magnitude(3), 1);
        assert_eq!(get_order_of_magnitude(9), 1);
        assert_eq!(get_order_of_magnitude(10), 2);
        assert_eq!(get_order_of_magnitude(32), 2);
        assert_eq!(get_order_of_magnitude(10_000), 5);
        assert_eq!(get_order_of_magnitude(10_001), 5);
        assert_eq!(get_order_of_magnitude(37_871), 5);
    }
}

combination.rs

pub struct PositionCombinations {
    min_length: usize,
    max_length: usize,
    state: Vec<bool>,
    finished: bool,
}

impl Iterator for PositionCombinations {
    type Item = Vec<bool>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let result = self.state.clone();
            self.increment();
            if self.finished {
                return None;
            }
            if (self.min_length..=self.max_length).contains(&result.iter().filter(|x| **x).count())
            {
                return Some(result);
            }
        }
    }
}

impl PositionCombinations {
    pub fn new(min_length: usize, max_length: usize, length: usize) -> Self {
        let state = vec![false; length];
        let finished = false;
        Self {
            min_length,
            max_length,
            state,
            finished,
        }
    }

    fn increment(&mut self) {
        let mut overflow = self.state[0];
        self.state[0] ^= true;
        for position in self.state[1..].iter_mut() {
            let new_overflow = *position & overflow;
            *position ^= overflow;
            overflow = new_overflow;
        }
        if overflow {
            self.finished = true;
        }
    }
}

pub trait ToString {
    fn to_string(&self) -> String;
}

impl ToString for Vec<bool> {
    fn to_string(&self) -> String {
        self.iter().map(|b| if *b { 'x' } else { '.' }).collect()
    }
}

#[cfg(test)]
mod test {
    use crate::combination::PositionCombinations;
    use std::collections::HashSet;

    #[test]
    fn test_combination_2_3_4() {
        let combinator = PositionCombinations::new(2, 3, 4);
        let result: Vec<_> = combinator.into_iter().collect();
        let mut number_solutions = result.len();
        let mut solution = HashSet::new();
        solution.insert(vec![false, false, true, true]);
        solution.insert(vec![false, true, false, true]);
        solution.insert(vec![false, true, true, false]);
        solution.insert(vec![false, true, true, true]);
        solution.insert(vec![true, true, false, false]);
        solution.insert(vec![true, false, true, false]);
        solution.insert(vec![true, false, false, true]);
        solution.insert(vec![true, false, true, true]);
        solution.insert(vec![true, true, false, true]);
        solution.insert(vec![true, true, true, false]);
        for item in solution {
            assert!(result.contains(&item));
            number_solutions -= 1;
        }
        assert_eq!(number_solutions, 0);
    }

    #[test]
    fn test_combination_2_2_3() {
        let combinator = PositionCombinations::new(2, 2, 3);
        let result: Vec<_> = combinator.into_iter().collect();
        let mut number_solutions = result.len();
        let mut solution = HashSet::new();
        solution.insert(vec![false, true, true]);
        solution.insert(vec![true, false, true]);
        solution.insert(vec![true, true, false]);
        for item in solution {
            assert!(result.contains(&item));
            number_solutions -= 1;
        }
        assert_eq!(number_solutions, 0);
    }
}

primes.rs

extern crate num;

use std::collections::HashSet;
use std::fmt::Display;
use std::hash::Hash;

use num::FromPrimitive;
use num::Num;
use num::ToPrimitive;

#[derive(Clone)]
pub struct Primes<T> {
    pub vector: Vec<T>,
    set: HashSet<T>,
}

impl<T> Primes<T>
where
    T: Num + ToPrimitive + FromPrimitive + Hash + Eq + PartialEq + Copy + Display,
{
    pub fn get_between(min_value: T, max_value: T) -> Self {
        let max_value = max_value.to_usize().unwrap();
        let min_value = min_value.to_usize().unwrap();
        assert!(min_value > 1);
        assert!(max_value > min_value);
        Self::from_array(
            &Self::get_prime_numbers_array(min_value, max_value),
            min_value,
            max_value,
        )
    }

    fn from_array(array: &[bool], min_value: usize, max_value: usize) -> Self {
        let number_of_primes = array.iter().filter(|b| **b).count();
        let mut vector = Vec::with_capacity(number_of_primes);
        let mut set = HashSet::with_capacity(number_of_primes);

        for number in min_value..max_value {
            let idx = number - min_value;
            // SAFETY: see considerations in get_prime_numbers_array
            if unsafe { *array.get_unchecked(idx) } {
                let prime = FromPrimitive::from_usize(number).unwrap();
                vector.push(prime);
                set.insert(prime);
            }
        }

        debug_assert_eq!(number_of_primes, vector.len());
        Primes { vector, set }
    }

    fn get_prime_numbers_array(min_value: usize, max_value: usize) -> Vec<bool> {
        // Sieve of Eratosthenes
        let length = max_value - min_value;
        let mut result = vec![true; length];

        let upper_limit = Self::calc_upper_limit(max_value);
        for i in 2..upper_limit {
            let skip = Self::find_number_to_skip_until_min_value(min_value, i);

            for multiple in (i * i..max_value).step_by(i).skip(skip) {
                let idx = multiple - min_value;
                // SAFETY: `multiple` will always be between min_value and max_value
                // (which define the length of the array), therfore idx is always smaller than the
                // length of result, therefore this access is always in bounds.
                // This is slightly faster than the bounds-checked write.
                unsafe { *result.get_unchecked_mut(idx) = false };
            }
        }
        result
    }

    fn calc_upper_limit(max_value: usize) -> usize {
        f64::sqrt(max_value as f64).ceil() as usize
    }

    fn find_number_to_skip_until_min_value(min_value: usize, i: usize) -> usize {
        ((min_value.saturating_sub(i * i)) as f64 / i as f64).ceil() as usize
    }

    pub fn contains(&self, val: &T) -> bool {
        self.set.contains(val)
    }
}

#[cfg(test)]
mod test {
    use super::Primes;

    #[test]
    fn test_example_prime() {
        let primes = Primes::get_between(2, 99_999);
        assert!(primes.set.contains(&56003));
        assert!(primes.set.contains(&56993));
        assert!(!primes.set.contains(&56002));
    }
}
\$\endgroup\$
0
\$\begingroup\$

I am not familiar with rust syntax but there are probably things you can improve:

  • Rust certainly has something nicer than commented out code like EXAMPLE 1 // const MIN_VALUE: Int = 10;. In C/C++ you could do this using compile-time flags like #ifdef TEST_SMALL
  • Why use Int = u64?
  • Comment at least briefly what every function does. For example, tell me in simple human terms what apply_transformation does.
  • Again I don't know how much rust syntax is necessary but I have a feeling combination.rs is way over-complicating the solution. To my eyes, the code is verbose to the point of not clarifying things but obscuring the idea which is actually pretty simple. You should also skip all generated values if that wasn't done yet (I can't tell)

I'll just give you my entire python solution and hope it gives you some ideas. Admittedly I wrote it in 2015 and it's not commented at all because it's "self-explanatory", so I would probably write a few things differently nowadays. It runs in 0.2 sec in pure python3.8.

# Search all primes, skipping seen cases (ex. 56**3)
from number import sieve

def family(max_test, family_size):
    primes = sieve(max_test)
    primes_set = set(primes)
    seen = set()

    for p in primes:
        sp = str(p)
        digits = list(sp[:-1])

        for d in digits:
            case = ''.join(['*' if c==d else c for c in sp])
            if case in seen:
                break
            else:
                seen.add(case)

            family = []
            for a in range(10):
                q = sp.replace(d, str(a))
                if q[0] != '0' and int(q) in primes_set:
                    family.append(int(q))

            if len(family) == family_size:
                print(case)
                return family[0]

print(family(10**6, 8))
  • Your Sieve of Eratosthenes implementation is written strangely in a while-loop style. I don't know why last_number appears to be carried over through loops? Normally it is written as two for loops, where you must skip already marked off primes. Otherwise you might just be doing trial division. In a functional style the trial-division sieve is often confused for the genuine sieve.
def sieve(n):
    nums = [0] * n
    for i in range(2, int(n**0.5)+1):
        if nums[i] == 0:
            for j in range(i*i, n, i):
                nums[j] = 1

    return [i for i in range(2, n) if nums[i] == 0]

I can't guarantee this is the fastest python sieve but it is fast enough for say primes up to 10^8. If you want to have a sieve for a huge range then you can implement a segmented sieve.

\$\endgroup\$
12
  • \$\begingroup\$ codereview.stackexchange.com/help/how-to-answer \$\endgroup\$
    – sarema
    Aug 15, 2022 at 20:55
  • \$\begingroup\$ If there is anything specific you want me to try to comment on, please say so. a passive-aggressive link comment helps nobody \$\endgroup\$
    – qwr
    Aug 15, 2022 at 21:03
  • 2
    \$\begingroup\$ I'd rather not. I don't mind any feedback, positive or negative, but picking up a post to present your own quick-and-dirty solution is not helpful. "I am not familiar with rust syntax" is the point where you could have realized your post is likely not helping. \$\endgroup\$
    – sarema
    Aug 15, 2022 at 21:09
  • 3
    \$\begingroup\$ I think your answer is inline with our rules as you have an IO. And we allow answers in another language then the OPs - an example. However community consensus was you should put more effort than normal in to get upvotes, or even no votes. Given you've said "hope it gives you some ideas" and you dismiss the OP, and our community's, concerns with "python is close enough to pseudocode" makes your answer worthy of downvotes. Additionally your point makes little sense when you haven't provided half the algorithm, where's sieve? \$\endgroup\$
    – Peilonrayz
    Aug 15, 2022 at 22:54
  • 1
    \$\begingroup\$ "IO" stands for "insightful observation", an explanation is available in the link sarema provided. Teaching people how to improve code is difficult as you need to build up from where the person is to your level. Your comments and answer suffer a lot from assumptions; understanding of Python, knowledge of sieves, lack of algorithms in the original code and OP's ability to infer algorithmic improvements. If you spend some time looking over the OP's code to see what your code improves algorithmically; and go on to edit the improvements in. Then please ping me, so I can remove the down vote. \$\endgroup\$
    – Peilonrayz
    Aug 16, 2022 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.