Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to know if there's a quick way to check if a number is semi-prime or not. By far all the links i have seen only tell either how to generate a semi prime or count the number of semi primes or to factorize it... but i just want to check whether it is or not. Please help me.

share|improve this question
    
There is no easy method. The best you can do is test if it is prime or not, then check for factors up to at most $n^{1/3}$ for divisibility. –  Foo Barrigno Jul 1 '13 at 17:09
    
@FooBarrigno If you are dealing with semi primes, then you have to check for factors up to the square root of n (n^1/2). Checking factors to the cube root of n (n^1/3) will do you no good if one of the factors is above cube root of n –  zerosofthezeta Jul 1 '13 at 17:40
1  
@diophantine - The OP wasn't trying to find a factor of the semiprime, only identify whether or not the number was a semiprime or not. Checking up to the cube root is sufficient in that case - because it rules out any number with 3 or more prime factors. –  Foo Barrigno Jul 1 '13 at 17:42
    
@FooBarrigno I might be mistaken, but semi prime refers to a number with ONLY two factors which are prime, so I don't see how you obtain the cube root of n. Could you please elaborate? –  zerosofthezeta Jul 1 '13 at 18:50
    
@diophantine - If you do not find a factor below the cube root of n, then you know that the number can only have 2 factors, and thus is a semi prime. If you DO find a factor below the cube root of n, then you need to check whether or not $n/q$ is prime. –  Foo Barrigno Jul 1 '13 at 19:05

3 Answers 3

David Broadhurst came up with a provable semiprime back in 2005, based on some ideas from Don Reble and Phil Carmody.

From MathWorld's semiprime -- "In 2005, Don Reble showed how an elliptic pseudo-curve and the Goldwasser-Kilian ECPP theorem could generate a 1084-digit provable semiprime without a known factorization (Reble 2005)."

It's not quick. For quick, you need relative small, factorable numbers.

share|improve this answer

For small numbers, the best method is to trial-divide by primes (or take the gcd with blocks of primes). If a prime factor is discovered, divide it out and test if the rest is prime or not. If no prime factor is found up to the cube root, it is semiprime if and only if it is not prime (assuming it is > 1). Usually the best order is trial dividing by the first hundred or so primes, checking if the number is itself prime, then finishing the trial division.

For large numbers, do a reasonable amount of trial division, check if the number is prime, run some ECM curves, then factor it completely (with SIQS or NFS, or perhaps even MPQS if the numbers are small enough). This is faster than trial division all the way up to the cube root.

The best way to find out what numbers are 'big' vs. 'small' is to implement both methods and test. As a order of magnitude, 1020 is probably the largest size where trial division outperforms ECM + MPQS.

It may be possible, for numbers of intermediate size, to use Strassen's algorithm (as improved by Costa & Harvey, building on Bostan, Gaudry, & Schost, themselves building on Chudnovsky & Chudnovsky's improvements on Strassen's original). Asymptotically, this takes time $O(n^{1/6}\log^{2+\varepsilon} n)$ compared to $O(n^{1/3}\log n)$ for trial division (using schoolbook division -- too small for Karatsuba) and $O(\exp(c(\log n)^{1/3}(\log\log n)^{2/3}))$ for the NFS. I haven't seen a practical implementation of this algorithm, so I can't speak to what its true breakpoints might be, but 1040 should be a rough upper bound.

share|improve this answer

I can find globally all the symmetrical general twin-primes once I have chosen the anchoring natural number n using the following Maxima programline:

for n from 2 thru 20 do print(sum(f(n,n-k,n+k)*(is(equal(primep(n-k)*primep(n+k),true^2))-unknown)/(true-unknown),k,0,n));

With equal displacement k from n, here are some simple results:

f(7,7,7)+f(7,3,11) f(8,5,11)+f(8,3,13) f(9,7,11)+f(9,5,13) f(10,7,13)+f(10,3,17) f(11,11,11)+f(11,5,17)+f(11,3,19) f(12,11,13)+f(12,7,17)+f(12,5,19) f(13,13,13)+f(13,7,19)+f(13,3,23) f(14,11,17)+f(14,5,23) f(15,13,17)+f(15,11,19)+f(15,7,23) f(16,13,19)+f(16,3,29) f(17,17,17)+f(17,11,23)+f(17,5,29)+f(17,3,31) f(18,17,19)+f(18,13,23)+f(18,7,29)+f(18,5,31) f(19,19,19)+f(19,7,31) f(20,17,23)+f(20,11,29)+f(20,3,37) (%o1) done

All are prime pairs some of which could qualify for semiprimes. With refinement you could have a program to sort out semiprimes, if you know the properties of semiprimes Frankly I don't quite know. Number theorists are not explicit enough.

Huen Yeong Kong dr

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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