Square-free semiprime counting

Question

Definition

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

The task

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

Answer 1

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(n_p²) where n_p 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

Answer 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}

Answer 3

Jelly, 7 bytes

ŒcfÆf€L

Try it online!

How it works

ŒcfÆf€L  Main link. Argument: n

Œ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.

Answer 4

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)])

Answer 5

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.

Answer 6

Ruby 82

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

Demo: http://ideone.com/cnm1Z

Answer 7

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!

Answer 8

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), 88 82 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.

Answer 9

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

Answer 10

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.

Answer 11

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

Answer 12

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!

Answer 13

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)
  +     add to running total

Run this one

Answer 14

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.

Answer 15

Retina, 58 bytes

_
¶_$`
%(`$
$"
,,`_(?=(__+)¶\1+$)
¶1$'
)C`1(?!(__+)\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 ...

)C`1(?!(__+)\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

Answer 16

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

Answer 17

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

Answer 18

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