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
  • oeis.org/A180074 ? – 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
  • 2
    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

11 Answers 11

up vote 5 down vote accepted

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
  • 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
  • 1
    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

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 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}
  • Fantastic, concise solution – ardnew Aug 6 '12 at 22:55
  • @ardnew Thanks. I enjoyed the challenge. – DavidC 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}}

Demo: http://ideone.com/cnm1Z

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

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!

  • 2
    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 at 7:58

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.
  • Wow, you made my attempt look embarrassing. Thanks for the ideas! – Harry May 5 at 6:09

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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