Definición

Un semiprime sin cuadrados es un número natural que es el producto de dos números primos distintos.

La tarea

Dado un número natural n, cuente todas las semiprimes sin cuadrados menores o iguales que n.

Detalles

Escriba una función o procedimiento que acepte un único parámetro entero y cuente todos los semiprimes sin cuadrados menores o iguales a su parámetro. El recuento debe ser un valor de retorno de una llamada de función o imprimirse en STDOUT.

Puntuación

La respuesta con el menor número de caracteres gana.

En caso de empate, se utilizarán los siguientes criterios en orden:

1. Persona más alta

2. Mejor complejidad temporal

3. La peor complejidad espacial

Ejemplos

f(1)     = 0
f(62)    = 18
f(420)   = 124
f(10000) = 2600

J, 50 40 38 37 caracteres

f=:3 :'+/y<:}.~.,(~:/**/)~p:i._1&p:y'

Uso:

   f 1
0
   f 62
18
   f 420
124
   f 10000
2600

Gracias a FUZxxl .

Prueba de rendimiento

   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 │   │
└───────┴──────┴────────┴────────┴─────┴────┴───┘

No soy un teórico como se ha visto aquí en el pasado, pero creo que la complejidad del tiempo es algo así como O (n _p ² ) donde n _p es el número de primos hasta e incluyendo el número de entrada n. Esto se basa en la suposición de que la complejidad de mi método (generar una tabla de multiplicación muy grande) supera con creces la complejidad de la función generadora principal incorporada en J.

Explicación

f=:3 :'...'declara un verbo (función) monádico. La entrada al verbo está representada por ydentro de la definición del verbo.

p:i._1&p:yEl p:verbo es los números primos de usos múltiples verbo, y se utiliza de dos maneras diferentes aquí: _1&p:ydevuelve el número de primos menos de yentonces p:i.genera cada uno de ellos. Usando 10 como entrada:

   p:i._1&p:10
2 3 5 7

(~:/**/)~genera la tabla de la que hablé anteriormente. */genera una tabla de multiplicación, ~:/genera una tabla no igual (para eliminar los cuadrados) y ambos se multiplican juntos. Usando nuestra salida anterior como entrada:

   */~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

}.~.,ahora convertimos los números en una lista, ,obtenemos los valores únicos ~.y eliminamos el 0 al comienzo}.

   }.~.,(~:/**/)~2 3 5 7
6 10 14 15 21 35

y<: Una comparación con la entrada original para verificar qué valores son válidos:

   10<:6 10 14 15 21 35
1 1 0 0 0 0

+/ y luego sume eso para obtener la respuesta.

   +/1 1 0 0 0 0
2

Mathematica 65 64 55 51 47 39

Código

Lo siguiente cuenta el número de semiprimes sin cuadrados menores o iguales a n:

FactorInteger@Range@n~Count~{a={_,1},a}

Cualquier factor semiprime sin cuadrados en una estructura de la forma: {{p,1}{q,1}} por ejemplo,

FactorInteger@221
(* out *)
{{13, 1},{17, 1}}

La rutina simplemente cuenta los números en el rango deseado que tienen esta estructura de factores.

Uso

n=62;
FactorInteger@Range@n~Count~{a={_,1},a}

(* out *)
18

Tiempo: todos los ejemplos dados

FactorInteger@Range@#~Count~{a = {_, 1}, a} & /@ {1, 62, 420, 10^4} // Timing

(* out *)
{0.038278, {0, 18, 124, 2600}}

Tiempo: n = 10 ^ 6

Se necesitan menos de cuatro segundos para contar el número de semi-primos sin cuadrados menores o iguales a un millón.

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

Jalea , 7 bytes

ŒcfÆf€L

Pruébalo en línea!

Cómo funciona

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

Pitón (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))

Proporcione algunos resultados de muestra para que los competidores puedan probar sus programas.

Rubí 82

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

Demostración: 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/

Demostración en línea aquí

Nota: En la demostración anterior, excluí los casos de prueba 420y 10000. Debido a la prueba de primalidad extremadamente ineficiente, no es posible hacer que el programa se ejecute para estas entradas en menos de 5 segundos.

Shell, 40

#! / bin / sh

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

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

Uso:

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

0m23.956s reales
usuario 0m23.601s
sys 0m0.404s

Jalea , 14 13 bytes

RÆEḟ0⁼1,1$Ɗ€S

Pruébalo en línea!

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!

La crítica constructiva bienvenida!

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

Pruébalo en línea!

Publicado en un desafío de 6 años porque establece un nuevo récord de Python, un IMO es un enfoque bastante interesante.

Explicación

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

Pruébalo en línea!

Basado en un golf de 92 bytes de Value Ink. Se necesita PyPy para interpretar correctamente 0or, porque Python estándar ve esto como un intento de un número octal.

Stax , 8 bytes

ߺ@N¬Që↔

Ejecutar y depurarlo

Desempaquetado, sin golf y comentado, se ve así.

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

Ejecute este

Perl 6 , 58 45 bytes

Gracias a Jo King por -13 bytes.

{+grep {3==.grep($_%%*)&&.all³-$_}o^*,1..$_}

Aprovecha el hecho de que los enteros con cuatro factores son semiprimes sin cuadrados o cubos perfectos.

Pruébalo en línea!

Brachylog , 7 bytes

{≥ḋĊ≠}ᶜ

Pruébalo en línea!

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

Pruébalo en línea!

Toma como entrada unaria con _marca de conteo

Explicación

Un número es un semi-primo sin cuadrado si su factor más grande y más pequeño, excluyéndose a sí mismo y 1, son ambos primos.

_
¶_$`

Toma la entrada y genera cada número unario menor o igual a él, cada uno en su propia línea

%(`

Entonces, para cada número ...

$
$"
,,`_(?=(__+)¶\1+$)
¶1$'

Encuentra su factor más pequeño y más grande, excluyéndose un 1 ...

)C`1(?!(__+)\1+¶)

y cuenta el número de ellos que es primo. Como el factor más pequeño debe ser primo, esto devuelve 1 o 2

2

Cuenta el número total de 2

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

Pruébalo en línea!

1 byte gracias al calamar 🦑

Ruby -rprime , 64 bytes

Sé que hay otra solución de Ruby aquí, pero no quería incluirla en los comentarios ya que fue respondida en 2012 ... y resulta que usar un indicador de programa lo cuenta como un idioma diferente , así que supongo que esto técnicamente no es "Ruby" de todos modos.

Pruébalo en línea!

Explicación

->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), caracteres 26, bytes 52

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

prueba:

  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

esta es una alternativa más larga (59 caracteres que preferiría)

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

prueba:

  h 1000000
209867