We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I converted the whole thing to Rust with I think the same time complexity, and it passes now
usestd::io::{self,BufRead};fnread_uint(stdin:&io::Stdin)->usize{letline:String=stdin.lock().lines().next().expect("fail").unwrap();matchline.trim().parse(){Ok(val)=>returnval,Err(_)=>panic!("input not an int: '{0:}'",line)}}/** * Generate all the primes up to 'upto' efficiently. */fnget_primes(upto:usize)->Vec<u64>{// The 'is_prime' is a list of odd numbers, so 0->1, 3->7, 11->23letmutis_prime:Vec<bool>=vec![true;upto/2];is_prime[0]=false;forodd_iin1usize..upto/2{if!is_prime[odd_i]{continue;}// Start removing at the number squaredletmutrm_i:usize=((2*odd_i+1).pow(2)-1)/2;whilerm_i<upto/2{// Take steps of 2x prime (once will be even)is_prime[rm_i]=false;rm_i+=2*odd_i+1;}}// Having discovered the indices of primes, store the remaining ones as a listletmutprimes:Vec<u64>=vec![2];forindin1..upto/2{ifis_prime[ind]{primes.push(2*indasu64+1);}}returnprimes;}/** * Do bisection to find a flipping point from true to false. */fnbisect<F,T>(vals:&Vec<T>,max_ind:usize,comp:F)->usizewhereT:Ord,F:Fn(&T)->bool{letmutlower:usize=0;letmutupper:usize=max_ind;// Keep iterating until bisection converges.loop{letmid:usize=(lower+upper)/2;ifcomp(&vals[mid]){upper=mid;}else{lower=mid;}// It has convergediflower>=upper-1{returnupper;}}}/** * Count the number of products of two primes (not necessarily distinct) that are less than 'n'. */fncount_products(limit:u64,primes:&Vec<u64>)->u32{// Find the highest prime index that needs to be considered (extra ones may have been pre-computed).letmax_ind:usize=bisect(&primes,primes.len()-1,|val:&u64|*val>limit);letmutcount:u32=0;// Pick one of the pair of primesfor(ind,leftprime)inprimes.iter().enumerate(){ifleftprime*primes[0]>=limit{break;}// Find for which 'right' 'left*right' starts being higher than 'limit'letflip_point=bisect(&primes,max_ind,|checkprime:&u64|leftprime*checkprime>=limit);// Only count those values where 'right >= left' (or reversed) to avoid duplicatesletb_val_count:usize=ifflip_point>ind{flip_point-ind}else{0};ifb_val_count<=0{// Not a single suitable 'rightprime' for this 'leftprime'; the rest will be worse, so quit.returncount;}count+=b_val_countasu32;}returncount;}fnmain(){letstdin:io::Stdin=io::stdin();letinp_cnt:usize=read_uint(&stdin);// Read all the inputsletmutinputs:Vec<usize>=vec![0;inp_cnt];forinp_iin0..inp_cnt{inputs[inp_i]=read_uint(&stdin);}// Calculate the necessary primesletmax_prime=*inputs.iter().max().unwrap();// todo: can I do with fewer primes, due to early stopping?letprimes=get_primes(max_prime);// Count the productsforinputininputs{letcount=count_products(inputasu64,&primes);println!("{}",count);}}
I think the complexity is N loglog N for searching prime numbers, and K N log N for searching products. For a * b, is searches each a (N)in the worst case, and uses bisection (log N) to find the first b for which a * b is too high.
If anyone knows any way to get the time complexity down further, let me know!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #187: Semiprimes
You are viewing a single comment's thread. Return to all comments →
I converted the whole thing to Rust with I think the same time complexity, and it passes now
I think the complexity is
N loglog N
for searching prime numbers, andK N log N
for searching products. Fora * b
, is searches eacha
(N
)in the worst case, and uses bisection (log N
) to find the firstb
for whicha * b
is too high.If anyone knows any way to get the time complexity down further, let me know!