# Square-free semiprime counting

## Definition

A square-free semiprime is a natural number that is the product of two distinct prime numbers.

Given a natural number `n`, count all square-free semiprimes less than or equal to `n`.

## Details

Please write a function or procedure that accepts a single integer parameter and counts all square-free semiprimes less than or equal to its parameter. The count must either be a return value of a function call or be printed to STDOUT.

## Scoring

The answer with the fewest number of characters wins.

In the event of a tie, the following criteria will be used in order:

1. Tallest person

2. Best time-complexity

3. Worst space-complexity

## Examples

``````f(1)     = 0
f(62)    = 18
f(420)   = 124
f(10000) = 2600
``````
-
– Ev_genus Aug 3 '12 at 0:50
oops, sorry, but no that sequence is not quite right due to the congruence restriction (e.g., 35=5*7 and 55=5*11 are not included). I will add a few example solutions to this particular problem momentarily. – ardnew Aug 3 '12 at 1:29
oeis.org/A006881 – Peter Taylor Aug 3 '12 at 7:07
What happens if a language doesn't have STDOUT (like javascript)? Use `console.log`? – Inkbug Aug 3 '12 at 11:23
@Inkbug isn't javascript capable of returning a value from a function? – ardnew Aug 3 '12 at 14:17
show 1 more comment

## J, 504038 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
``````
-
Do you have a phony version of this program (phony as the opposite of tacit)? 13 is not always giving the most efficient tacit code. – FUZxxl Aug 3 '12 at 13:22
No, I didn't use 13 in this case - though I think I probably did what it would have done had I tried. The code is basically: `+/-.x<}.~.,(~:/~*[*/])p:i._1&p:[x=.n` where n is the input. – Gareth Aug 3 '12 at 13:34
Why not just `f=:3 :'+/-.y<}.~.,(~:/~*[*/])p:i._1&p:y'` for 40 characters? – FUZxxl Aug 3 '12 at 13:41
Thanks, I never even considered using `3 :'...'` – Gareth Aug 3 '12 at 13:45
Would you publish some timing results so we can judge the efficiency of the program? – David Carraher Aug 3 '12 at 17:50
show 6 more comments

## 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)])
``````
-
 `f=lambda x:sum([(i*j<=x)&p(j)&p(i)for i in r(2,x)for j in r(2,i)])` saves 5 characters. – beary605 Aug 3 '12 at 6:56 @beary605: Thanks, but I think that it will take way too long without short circuiting. – grc Aug 3 '12 at 7:21 voting you up. too many thoughts about `itertools` in my head. – Ev_genus Aug 3 '12 at 16:31

# Mathematica 6564555147 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}
``````
-
 Fantastic, concise solution – ardnew Aug 6 '12 at 22:55 @ardnew Thanks. I enjoyed the challenge. – David Carraher Aug 7 '12 at 14:01

## Python (139)

``````from itertools import*;s=lambda n:sum(x*y<=n and x<y for x,y in product(filter(lambda x:all(x%i for i in range(2,x)),range(2,n)),repeat=2))
``````

Please provide some sample results so competitors could test their programs.

-
 see, you didn't even need the examples! :^) – ardnew Aug 3 '12 at 1:44

## Ruby 82

``````z=->n{[*2..n].select{|r|(2...r).all?{|m|r%m>0}}.combination(2).count{|a,b|a*b<=n}}
``````
-

# Python 139

``````def f(n):
p=[];c=0
for i in range(2,n+1):
if all(i%x for x in p):p+=[i]
c+=any((0,j)[i/j<j]for j in p if i%j==0 and i/j in p)
return c
``````
-

## Golfscript 64

``````~:ß,{:§,{)§\%!},,2=},0+:©{©{1\$}%\;2/}%{+}*{..~=\~*ß>+\0?)+!},,2/
``````

Online demo here

Note: In the demo above I excluded the `420` and `10000` test cases. Due to the extremely inefficient primality test, it's not possible to get the program to execute for these inputs in less than 5 seconds.

-

## Shell, 40

```#!/bin/sh

seq \$1|factor|awk 'NF==3&&\$2!=\$3'|wc -l

#old, 61
#seq \$1|factor|awk 'BEGIN{a=0}NF==3&&\$2!=\$3{a++}END{print a}'
```

Usage:

```\$ ./count 1
0
\$ ./count 420
124
\$ ./count 10000
2600
\$ time ./cnt.sh 1000000
209867

real    0m23.956s
user    0m23.601s
sys     0m0.404s
```
-