use machine_prime::{is_prime,is_prime_wc};
/*
   Some examples of serious research implementations. 
   These are all simplified implementations as used in the f-analysis library.  
   Machine-prime performs better than Erastothenes sieve for searching for primes of certain form
   Fortunately this is the majority of number-theoretic research applications
   
   An example of certain primes that we can look for are ones such that ((p-1)/4)*2 +1 are also prime. 
   These comprise the semiprimes that satisfy the Monier-Rabin bound, and can be used for constructing
   strong fermat base sets. 
   
   An simple implementation is provided below for all the semiprimes that satisfy the Monier-Rabin bound. 
   A realistic implementation is going to use Erastothenes sieve for the first primes, 
   and Machine-prime to determine the counterpart.
   
*/
// 13172894
fn mr_count() -> u64{
  let mut count = 0u64;
   for lhs in 0..1u64<<32{
     if is_prime(lhs){
        // Construct the candidate integer
        let rhs = (((lhs-1)>>2)<<1)+1;
        // Check if candidate integer is also prime
        if is_prime(rhs){
        // Check if lhs*rhs is less than 2^64
         //  let (_,flag) = lhs.overflowing_mul(rhs);
           // Break loop if computation overflowed
          // if flag{
          // println!("{}",lhs);
          //   break;
          
           // Count all the Monier-Rabin semiprimes
           count+=1;
        }
     }
   }
   count
}

fn carmichael(x: u64) -> Vec<u64>{
  let mut candidate_primes = vec![];
  
  let bound = (x as f64/100f64).sqrt() as u64;
  
  for i in 0..bound{
    if i%4 == 3 && is_prime(i){
      candidate_primes.push(i);
    }
  }
  println!("{}", candidate_primes.len());
  let mut carmichaels = vec![];
  
  for i in candidate_primes.iter(){
    for j in candidate_primes.iter(){
      for k in candidate_primes.iter(){
      
      let n = (*i* *j* *k);
      let n_minus = n-1;
        if n_minus % (*i-1) == 0 && n_minus%(*j-1)==0  && n_minus%(*k-1) ==0{
          carmichaels.push(n);
        }
        
      }
    }
  }
  return carmichaels
}

/*

*/
//fn res_prime_count() ->  
fn main(){

  let start = std::time::Instant::now();
  let count  = carmichael(1u64<<40);//mr_count();
  let stop = start.elapsed();
  
  println!("{:?} {:?}",count,stop)
}