Square-free semiprime counting
J, 50 40 38 37 characters
f=:3 :'+/y<:}.~.,(~:/**/)~p:i._1&p:y'
Usage:
f 1
0
f 62
18
f 420
124
f 10000
2600
With thanks to FUZxxl.
Performance test
showtotal_jpm_ ''[f 1[start_jpm_ ''
Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name │locale│all │here │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f │base │0.000046│0.000046│100.0│100 │1 │
│[total]│ │ │0.000046│100.0│100 │ │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
showtotal_jpm_ ''[f 1[f 62[start_jpm_ ''
Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name │locale│all │here │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f │base │0.000095│0.000095│100.0│100 │2 │
│[total]│ │ │0.000095│100.0│100 │ │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
showtotal_jpm_ ''[f 1[f 62[f 420[start_jpm_ ''
Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name │locale│all │here │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f │base │0.000383│0.000383│100.0│100 │3 │
│[total]│ │ │0.000383│100.0│100 │ │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[start_jpm_ ''
Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name │locale│all │here │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f │base │0.084847│0.084847│100.0│100 │4 │
│[total]│ │ │0.084847│100.0│100 │ │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[f 50000[start_jpm_ ''
Time (seconds)
┌───────┬──────┬────────┬────────┬─────┬────┬───┐
│name │locale│all │here │here%│cum%│rep│
├───────┼──────┼────────┼────────┼─────┼────┼───┤
│f │base │5.014691│5.014691│100.0│100 │5 │
│[total]│ │ │5.014691│100.0│100 │ │
└───────┴──────┴────────┴────────┴─────┴────┴───┘
I'm no theoretician as has been seen here in the past, but I think the time complexity is something like O(np2) where np is the number of primes up to and including the input number n. This is based on the assumption that the complexity of my method (generating a very large multiplication table) far outweighs the complexity of the prime generating function built in to J.
Explanation
f=:3 :'...' declares a (monadic) verb (function). The input to the verb is represented by y within the verb definition.
p:i._1&p:y The p: verb is the multi purpose primes verb, and it's used in two different ways here: _1&p:y returns the number of primes less than y then p:i. generates every one of them. Using 10 as input:
p:i._1&p:10
2 3 5 7
(~:/**/)~ generates the table I spoke of earlier. */ generates a multiplication table, ~:/ generates a not-equal table (to eliminate the squares) and both of these are multiplied together. Using our previous output as input:
*/~2 3 5 7
4 6 10 14
6 9 15 21
10 15 25 35
14 21 35 49
~:/~2 3 5 7
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
(~:/**/)~2 3 5 7
0 6 10 14
6 0 15 21
10 15 0 35
14 21 35 0
}.~., now we turn the numbers into one list , get the unique values ~. and remove the 0 at the start }.
}.~.,(~:/**/)~2 3 5 7
6 10 14 15 21 35
y<: a comparison with the original input to check which values are valid:
10<:6 10 14 15 21 35
1 1 0 0 0 0
+/ and then sum that to get the answer.
+/1 1 0 0 0 0
2
Mathematica 65 64 55 51 47 39
Code
The following counts the number of square-free semiprimes less than or equal to n:
FactorInteger@Range@n~Count~{a={_,1},a}
Any square-free semiprime factors into a structure of the form: {{p,1}{q,1}}
For example,
FactorInteger@221
(* out *)
{{13, 1},{17, 1}}
The routine simply counts the numbers in the desired range that have this structure of factors.
Usage
n=62;
FactorInteger@Range@n~Count~{a={_,1},a}
(* out *)
18
Timing: All the given examples
FactorInteger@Range@#~Count~{a = {_, 1}, a} & /@ {1, 62, 420, 10^4} // Timing
(* out *)
{0.038278, {0, 18, 124, 2600}}
Timing: n=10^6
It takes under four seconds to count the number of square-free semi-primes less than or equal to one million.
n=10^6;
FactorInteger@Range@n~Count~{a = {_, 1}, a}//Timing
(* out *)
{3.65167, 209867}
Python, 115
r=range
p=lambda x:all(x%i for i in r(2,x))
f=lambda x:sum([i*j<=x and p(j)and p(i)for i in r(2,x)for j in r(2,i)])