# Project Euler #187: Semiprimes

# Project Euler #187: Semiprimes

riyadali + 1 comment Java was used to create a working solution that ran in under 2 seconds for the worst case scenarion (20 testcases with N having a maximum value of 100 million in all of these cases and each test result was computed independently -- so no time savings because the testcase was the same in all of these instances)

The challenging part of this solution was efficently computing the primes up to 50 million (maximum N divided by smallest prime) and saving them in an array. This is done once. This array is then referenced in all of the test cases to produce the results desired.

mark_verleg + 0 comments [deleted]

andres_puente21 + 0 comments Where can I find the input and expected output for each test case?

nickk2002 + 0 comments why 5 is semiprime? 5 = 5*1 is only one single prime number, not two

Premprakash1234 + 1 comment Can sum1 explain me how the sample out put answer is 1 for the input of 5. ? condition of N is shd strt from 5 and input value itself 5 so only one value ie 5.

so how 5 value contains 2 prime factors ? if(1 and 5) then all the provided example input was wrong isnt it ?

Thanks in advance

_master + 0 comments The output we've to give is no. of semiprimes less than 5. Only semiprime less than 5 is 4. hence answer is 1.

ujjal_123 + 0 comments # include

# include

# include

# include

int factor(int y);int prime(int x);

int main() { int i,n=0,t,c=0; scanf("%d",&t); for(;t>0;t--){ scanf("%d",&n); if(n<=4){ printf("\0\n"); exit; for(i=4;i if (factor(i)==1) c++; return 1;

printf("%d\n",c);} int factor(int n){ int i,ctr=0,m=1; while(m!=n){ for(i=2;i<=n;i++){ number: if(n%i==0 && prime(i)==1) m*=i; if(m==n) return 1; else goto number;

}`} }`

} int prime(int x){ int i,c=0; for(i=1;i<=x;i++) if (x%i==0) c++; if(c==2) return 1; }

whats the compiler error in this code

shubhubanachauh1 + 0 comments # include

# include

# include

using namespace std; int main() { int t; long long int n; double c=0; double k=0; cin>>t; long long int i; long long int j; while(t--) { cin>>n; vector v; for(i=2;i<=n;i++) { j=1; while(j<=i/2) { if(i%j==0) c+=1; j++; } if(c==1 && ((2*i)<=n)) { v.insert(v.begin()+k,i); k+=1; } c=0; } k=0; for(i=0;i } } what is the problem is my code

sumantopal07 + 0 comments my code is showing timeout error...any minor changes i should make in the algorithm??

def primefactors(n): m=n a=[] while n%2==0: a.append(2) if len(a)==3: return(-1) n=n//2 for i in range(3,(m//2)+1,2): while n%i==0: a.append(i) if len(a)==3: return(-1) n=n//i if len(a)==2: return(m) n=int(input()) for i in range(n): y=int(input()) count=0 for j in range(2,y): if primefactors(j)==j: count=count+1 print(count)

prunns + 1 comment Can someone help deduce a formula to calculate the number of Prime Numbers that comes before a certain number, say x.

The closest i could reach was with an approximate function f(x) as:

`f(x)=x/(log x -1);`

riyadali + 1 comment This wiki article is quite comprehensive https://en.wikipedia.org/wiki/Prime-counting_function and also quite complex. Good luck on reading through it!!!

My feeling is that there is no way to exactly know how many prime numbers there are less that a certain number without actually generating the prime numbers themselves. You can aproximate the number of primes but you would never be able to know exactly without generating the numbers. My reasoning behind this is that as far as I know there is currently no formula to generate the nth prime number and since there is no formula then there would be no way to accurately (that is exactly) say how many of them there are.

But I'm no mathematician, and I'm sure others on this forum are way smarter than I am and would be able to lead you in the proper directions or share some other insights. I'm just using plain old common sense in my reasoning above.

prunns + 0 comments Thanks for getting back. I am very well convinced that in order to find the exact number of primes that occur before a given number is only possible by generating them. Checked out the link above, but the results show that those functions give close but approximate results only. I guess i will figure out a way for that. Thanks again.

mark_verleg + 1 comment Does anyone have any hints how to make this Python code faster? Is it possible to get it fast enough without converting to C? I thought my algorithm is already fairly optimal but apparently not.

The idea is basically to get all the primes, then for each prime

`a`

, use bisection to find the prime`b`

where`a * b > N`

. So I would say the complexity is`T N log N`

for that part and`N loglog N`

for finding primes.from sys import stdin def get_primes(upto): candidates = set(range(3, upto + 1, 2)) for current in range(1, upto + 1, 2): if current not in candidates: continue for multiple in range(current**2, upto, current): candidates.discard(multiple) return [2] + sorted(candidates) def count_products(N, primes): count = 0 for ind, a in enumerate(primes): if a * primes[0] >= N: break lower, upper = 0, len(primes) - 1 for k in range(len(primes)): mid = (upper + lower) // 2 b = primes[mid] if a * b >= N: upper = mid else: lower = mid if lower >= upper - 1: b_val_count = max(upper - ind, 0) if b_val_count <= 0: return count count += b_val_count break return count T = int(stdin.readline()) Ns = [] for _ in range(T): Ns.append(int(stdin.readline())) primes = get_primes(max(Ns)) for N in Ns: count = count_products(N, primes) print(count)

mark_verleg + 0 comments I converted the whole thing to Rust with I think the same time complexity, and it passes now

use std::io::{self, BufRead}; fn read_uint(stdin : &io::Stdin) -> usize { let line: String = stdin.lock().lines().next().expect("fail").unwrap(); match line.trim().parse() { Ok(val) => return val, Err(_) => panic!("input not an int: '{0:}'", line) } } /** * Generate all the primes up to 'upto' efficiently. */ fn get_primes(upto : usize) -> Vec<u64> { // The 'is_prime' is a list of odd numbers, so 0->1, 3->7, 11->23 let mut is_prime : Vec<bool> = vec![true; upto / 2]; is_prime[0] = false; for odd_i in 1usize .. upto / 2 { if !is_prime[odd_i] { continue; } // Start removing at the number squared let mut rm_i : usize = ((2 * odd_i + 1).pow(2) - 1) / 2; while rm_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 list let mut primes : Vec<u64> = vec![2]; for ind in 1 .. upto / 2 { if is_prime[ind] { primes.push(2 * ind as u64 + 1); } } return primes; } /** * Do bisection to find a flipping point from true to false. */ fn bisect<F, T>(vals : &Vec<T>, max_ind : usize, comp : F) -> usize where T: Ord, F: Fn(&T) -> bool { let mut lower : usize = 0; let mut upper : usize = max_ind; // Keep iterating until bisection converges. loop { let mid : usize = (lower + upper) / 2; if comp(&vals[mid]) { upper = mid; } else { lower = mid; } // It has converged if lower >= upper - 1 { return upper; } } } /** * Count the number of products of two primes (not necessarily distinct) that are less than 'n'. */ fn count_products(limit : u64, primes : &Vec<u64>) -> u32 { // Find the highest prime index that needs to be considered (extra ones may have been pre-computed). let max_ind : usize = bisect(&primes, primes.len() - 1, |val : &u64| *val > limit); let mut count : u32 = 0; // Pick one of the pair of primes for (ind, leftprime) in primes.iter().enumerate() { if leftprime * primes[0] >= limit { break; } // Find for which 'right' 'left*right' starts being higher than 'limit' let flip_point = bisect(&primes, max_ind, |checkprime : &u64| leftprime * checkprime >= limit); // Only count those values where 'right >= left' (or reversed) to avoid duplicates let b_val_count : usize = if flip_point > ind { flip_point - ind } else { 0 }; if b_val_count <= 0 { // Not a single suitable 'rightprime' for this 'leftprime'; the rest will be worse, so quit. return count; } count += b_val_count as u32; } return count; } fn main() { let stdin : io::Stdin = io::stdin(); let inp_cnt : usize = read_uint(& stdin); // Read all the inputs let mut inputs: Vec<usize> = vec![0; inp_cnt]; for inp_i in 0 .. inp_cnt { inputs[inp_i] = read_uint(& stdin); } // Calculate the necessary primes let max_prime = *inputs.iter().max().unwrap(); // todo: can I do with fewer primes, due to early stopping? let primes = get_primes(max_prime); // Count the products for input in inputs { let count = count_products(input as u64, &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!

mark_verleg + 0 comments Just in case anyone else also misreads the question and thinks you need to check a single number for subprime-ness very fast, here is my Python solution (so this does

**not**solve the problem). It uses only factors up to sqrt(N) which is several orders of magnitude faster.from math import ceil, sqrt def is_indivisible_by(nr, primes): # Ckeck whether nr is prime, but only using pre-computed list of factors for check_prime in primes: if nr % check_prime != 0: return False return True def count_factors(N, primes, max_known): fac_cnt = 0 # Check if the number is divisible by prime factors for check_prime in primes: remainder = N # Check if N is divisible by p multiple times while remainder % check_prime == 0: remainder //= check_prime fac_cnt += 1 if fac_cnt > 2: return 3 if remainder < N and remainder != 1: # Check whether the 'complement' of factor p is a prime if is_indivisible_by(remainder, primes): # Complement not prime, so 3+ factors (1 for remainder and 2 for complement) return 3 elif remainder > max_known: # Prime that's higher than what we check, so add a factor fac_cnt += 1 if fac_cnt > 2: return 3 return fac_cnt def expand_primes(primes, highest, upto): # Find more primes if we don't have enough yet for new_prime in range(highest, upto + 1): highest += 1 for check_prime in primes: if highest % check_prime == 0: break else: primes.append(highest) return highest, primes def do_for_Ns(Ns): # Solve for several Ns, doing Ns from low to high to need minimal prime factors results = {} primes = [] max_known = 1 for N in sorted(Ns): # Expand primes if we don't know enough # Note that the sqrt trick brings is down from 2m46s to 0m0.03s max_known, primes = expand_primes(primes, highest=max_known, upto=int(ceil(sqrt(N)))) # Find the number of prime factors, cutting out at 2 fac_cnt = count_factors(N, primes, max_known) results[N] = fac_cnt for N in Ns: print('{0:3d} ~ {1:d} {2:s}'.format(N, results[N], '**' if results[N] == 2 else '')) # do_for_Ns(range(1, 31)) do_for_Ns([919 * 919, 919 * 929, 863 * 1217, 3 * 73823, 113 * 103 * 101, 103 * 103 * 103, 2 * 2 * 73823, int(2**20)])

Sort 21 Discussions, By:

Please Login in order to post a comment