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.
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.
frommathimportceil,sqrtdefis_indivisible_by(nr,primes):# Ckeck whether nr is prime, but only using pre-computed list of factorsforcheck_primeinprimes:ifnr%check_prime!=0:returnFalsereturnTruedefcount_factors(N,primes,max_known):fac_cnt=0# Check if the number is divisible by prime factorsforcheck_primeinprimes:remainder=N# Check if N is divisible by p multiple timeswhileremainder%check_prime==0:remainder//=check_primefac_cnt+=1iffac_cnt>2:return3ifremainder<Nandremainder!=1:# Check whether the 'complement' of factor p is a primeifis_indivisible_by(remainder,primes):# Complement not prime, so 3+ factors (1 for remainder and 2 for complement)return3elifremainder>max_known:# Prime that's higher than what we check, so add a factorfac_cnt+=1iffac_cnt>2:return3returnfac_cntdefexpand_primes(primes,highest,upto):# Find more primes if we don't have enough yetfornew_primeinrange(highest,upto+1):highest+=1forcheck_primeinprimes:ifhighest%check_prime==0:breakelse:primes.append(highest)returnhighest,primesdefdo_for_Ns(Ns):# Solve for several Ns, doing Ns from low to high to need minimal prime factorsresults={}primes=[]max_known=1forNinsorted(Ns):# Expand primes if we don't know enough# Note that the sqrt trick brings is down from 2m46s to 0m0.03smax_known,primes=expand_primes(primes,highest=max_known,upto=int(ceil(sqrt(N))))# Find the number of prime factors, cutting out at 2fac_cnt=count_factors(N,primes,max_known)results[N]=fac_cntforNinNs:print('{0:3d} ~ {1:d}{2:s}'.format(N,results[N],'**'ifresults[N]==2else''))# 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)])
Project Euler #187: Semiprimes
You are viewing a single comment's thread. Return to all 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.