# 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

## 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? – DavidC Aug 3 '12 at 17:50

# 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. – DavidC Aug 7 '12 at 14:01
• Nice! Question: are those space characters around the = and after the , actually needed syntactically? – Todd Lehman Jun 2 at 23:11
• @ToddLehman, You are right. I removed them. (They had not been counted so the byte count stays the same.) – DavidC Jun 3 at 13:08

## 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

# Jelly, 7 bytes

ŒcfÆf€L

Try it online!

### How it works

Œc       Generate all 2-combinations of [1, ..., n], i.e., all pairs [a, b] such
that 1 ≤ a < b ≤ n.
Æf€   Compute the prime factorization of each k in [1, ..., n].
f      Filter; keep only results that appear to the left and to the right.
L  Take the length.
• Wow, you made my attempt look embarrassing. Thanks for the ideas! – Harry May 5 '18 at 6:09

## 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

~:ß,{:§,{)§\%!},,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 # Jelly, 14 13 bytes RÆEḟ0⁼1,1$Ɗ€S

Try it online!

RÆEḟ0⁼1,1$Ɗ€S main function: RÆE get the prime factorization Exponents on each of the Range from 1 to N, Ɗ€ apply the preceding 1-arg function composition (3 funcs in a row) to each of the prime factorizations: (the function is a monadic semiprime checker, as per DavidC's algorithm) ḟ0 check if the factors minus the zero exponents... ⁼1,1$      ...are equal to the list [1,1]
S   take the Sum of those results, or number of successes!

Constructive criticism welcomed!

• This combination of and S can be turned into a use of ċ (Count). You can get down to 10 bytes using it. I'll let you work it out! – Lynn May 5 '18 at 7:58

# Python 2/3, 95 94 bytes

lambda n:sum(map(F,range(n+1)))
F=lambda x,v=2:sum(x%i<1and(F(i,0)or 3)for i in range(2,x))==v

Try it online!

Posted in a 6 year old challenge because it sets a new Python record, an IMO it's a pretty interesting approach.

# Explanation

lambda n:sum(map(F,range(n+1)))           # Main function, maps F ("is it a semiprime?")
#  over the range [0, n]
F=lambda x,v=2:                           # Helper function; "Does x factor into v
#  distinct prime numbers smaller than itself?"
sum(                                    # Sum over all numbers i smaller than x
x%i<1                                 # If i divides x,
and                                   #  then
(F(i,0)                               #  add 1 if i is prime (note that F(i,0)
#  is just a primality test for i!)
or 3)                                 #  or 3 if i is not prime (to make F
#  return False)
for i in range(2,x))
==v                                     # Check if there were exactly v distinct prime
#  factors smaller than x, each with
#  multiplicity 1

# Python 2/3 (PyPy), 8882 81 bytes

lambda n:sum(sum(x%i<1and(x/i%i>0or 9)for i in range(2,x))==2for x in range(n+1))

Try it online!

Based on a 92-byte golf by Value Ink. PyPy is needed to correctly interpret 0or, because standard Python sees this as an attempt at an octal number.

# Stax, 8 bytes

ßº@N¬Që↔

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

F       for 1..n run the rest of the program
:F    get distinct prime factors
2(    trim/pad factor list to length 2
:*    compute product of list
_/    integer divide by initial number (yielding 0 or 1)

Run this one

# Perl 6, 58 45 bytes

Thanks to Jo King for -13 bytes.

{+grep {3==.grep($_%%*)&&.all³-$_}o^*,1..$_} Takes advantage of the fact that integers with four factors are either square-free semiprimes or perfect cubes. Try it online! # Brachylog, 7 bytes {≥ḋĊ≠}ᶜ Try it online! The output is { }ᶜ the number of ways in which you could ≥ choose a number less than or equal to the input ḋ such that its prime factorization Ċ is length 2 ≠ with no duplicates. # Retina, 58 bytes _ ¶_$
%("
,,_(?=(__+)¶\1+$) ¶1$'
)C1(?!(__+)\1+¶)
2

Try it online!

Takes as input unary with _ as tally mark

## Explanation

A number is a square-free semi-prime if its largest and smallest factor, excluding itself and 1, are both primes.

_
¶_$ Takes the input and generate each unary number less than or equal to it, each on its own line %( Then, for each number ...$
$" ,,_(?=(__+)¶\1+$)
¶1\$'

Find its smallest and largest factor, excluding itself an 1 ...

)C1(?!(__+)\1+¶)

and count the number of them that is prime. Since the smallest factor must be a prime, this returns 1 or 2

2

Count the total number of 2's

# Python 2, 105 104 bytes

lambda m:sum(reduce(lambda(a,v),p:(v*(a+(n%p<1)),v>0<n%p**2),range(2,n),(0,1))[0]==2for n in range(m+1))

Try it online!

1 byte thx to squid 🦑

• (p*p) can be p**2 – squid Jun 3 at 17:23

# Ruby-rprime, 64 bytes

I know that there's another Ruby solution here, but I didn't want to bump it with comments since it was answered in 2012... and as it turns out, using a program flag counts it as a different language, so I guess this technically isn't "Ruby" anyhow.

Try it online!

Explanation

->n{(1..n).count{|i|m=i.prime_division;m.size|m.sum(&:last)==2}}
->n{                                    # Anonymous lambda
(1..n).count{|i|                    # Count all from 1 to n that match
# the following condition
m=i.prime_division;     # Get the prime factors of i as
#  base-exponent pairs (e.g. [2,3])
m.size                  # Size of factors (# of distinct primes)
|                 # bit-or with...
m.sum(&:last)    # Sum of the last elements in the pairs
#  (the sum of the exponents)
==2 # Check if that equals 2 and return.
# Because 2 is 0b10, the bit-or means
#  that the condition is true iff both
#  are either 2 or 0, but because this
#  is a prime factorization, it is
#  impossible to have the number of
#  distinct primes or the sum of the
#  exponents to equal 0 for any number
#  > 1. (And for 1, size|sum == 0.)
}                                   # End count block
}                                       # End lambda

# APL(NARS), chars 26, bytes 52

{≢b/⍨{(⍵≡∪⍵)∧2=≢⍵}¨b←π¨⍳⍵}

test:

f←{≢b/⍨{(⍵≡∪⍵)∧2=≢⍵}¨b←π¨⍳⍵}
f 1
0
f 9
1
f 62
18
f 420
124
f 1000
288
f 10000
2600
f 100000
23313

this is a longer alternative (59 chars that i would prefer)

r←h w;n;t
n←4⋄r←0
n+←1⋄→0×⍳w<n⋄→2×⍳(2≠≢t)∨2≠≢∪t←πn⋄r+←1⋄→2

test:

h 1000000
209867