Definição

Um semiprime sem quadrado é um número natural que é o produto de dois números primos distintos.

A tarefa

Dado um número natural n, conte todos os semiprimes sem quadrados, iguais ou inferiores a n.

Detalhes

Por favor, escreva uma função ou procedimento que aceite um único parâmetro inteiro e conte todos os semiprimes livres de quadrados menores ou iguais ao seu parâmetro. A contagem deve ser um valor de retorno de uma chamada de função ou ser impressa em STDOUT.

Pontuação

A resposta com o menor número de caracteres vence.

Em caso de empate, os seguintes critérios serão usados ​​em ordem:

1. Pessoa mais alta

2. Melhor complexidade de tempo

3. Pior complexidade de espaço

Exemplos

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

Com agradecimentos a FUZxxl .

Teste de performance

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

Não sou um teórico, como já vimos aqui no passado, mas acho que a complexidade do tempo é algo como O (n _p ² ), em que n _p é o número de primos até e incluindo o número de entrada n. Isso se baseia na suposição de que a complexidade do meu método (gerando uma tabela de multiplicação muito grande) supera em muito a complexidade da função de geração principal incorporada a J.

Explicação

f=:3 :'...'declara um verbo (monádico) (função). A entrada para o verbo é representada por ydentro da definição de verbo.

p:i._1&p:yO p:verbo é o verbo primos multiuso, e é usado de duas maneiras diferentes aqui: _1&p:yretorna o número de primos menor do que yentão p:i.gera cada um deles. Usando 10 como entrada:

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

(~:/**/)~gera a tabela da qual falei anteriormente. */gera uma tabela de multiplicação, ~:/gera uma tabela não-igual (para eliminar os quadrados) e ambos são multiplicados juntos. Usando nossa saída 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

}.~.,agora transformamos os números em uma lista, ,obtemos os valores exclusivos ~.e removemos o 0 no início}.

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

y<: uma comparação com a entrada original para verificar quais valores são válidos:

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

+/ e depois some isso para obter a resposta.

   +/1 1 0 0 0 0
2

Mathematica 65 64 55 51 47 39

Código

A seguir, conta o número de semiprimes livres de quadrados menores ou iguais a n:

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

Quaisquer fatores semiprimes livres de quadrados em uma estrutura do formulário: {{p,1}{q,1}} por exemplo,

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

A rotina simplesmente conta os números no intervalo desejado que possuem essa estrutura de fatores.

Uso

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

(* out *)
18

Tempo: Todos os exemplos dados

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

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

Tempo: n = 10 ^ 6

Leva menos de quatro segundos para contar o número de semi-primos sem quadrado menor ou igual a um milhão.

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

Geléia , 7 bytes

ŒcfÆf€L

Experimente online!

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

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

Forneça alguns resultados de amostra para que os concorrentes possam testar seus programas.

Ruby 82

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

Demonstração: 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/

Demonstração online aqui

Nota: Na demo acima eu excluídos os 420e 10000teste casos. Devido ao teste de primalidade extremamente ineficiente, não é possível executar o programa para essas entradas em menos de 5 segundos.

Shell, 40

#! / bin / sh

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

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

Uso:

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

0m23.956s reais
usuário 0m23.601s
sys 0m0.404s

Geléia , 14 13 bytes

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

Experimente 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!

Críticas construtivas bem-vindas!

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

Experimente online!

Publicado em um desafio de 6 anos, porque estabelece um novo recorde em Python; para a IMO, é uma abordagem bastante interessante.

Explicação

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

Experimente online!

Baseado em um golfe de 92 bytes da Value Ink. O PyPy é necessário para interpretar corretamente 0or, porque o Python padrão vê isso como uma tentativa de um número octal.

Stax , 8 bytes

ߺ@N¬Që↔

Execute e depure

Descompactado, não jogado e comentado, parece com isso.

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

Execute este

Perl 6 , 58 45 bytes

Agradecimentos a Jo King por -13 bytes.

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

Aproveita o fato de que números inteiros com quatro fatores são semiprimes sem quadrado ou cubos perfeitos.

Experimente online!

Braquilog , 7 bytes

{≥ḋĊ≠}ᶜ

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

Experimente online!

Toma como entrada unária com _como marca de contagem

Explicação

Um número é um semi-primo sem quadrados, se o maior e o menor fator, excluindo-se ele e 1, forem primos.

_
¶_$`

Pega a entrada e gera cada número unário menor ou igual a ele, cada um em sua própria linha

%(`

Então, para cada número ...

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

Encontre o menor e o maior fator, excluindo-se 1 ...

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

e conte o número deles que é primo. Como o menor fator deve ser primo, isso retorna 1 ou 2

2

Conte o número total de 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))

Experimente online!

1 byte thx para squid 🦑

Ruby -rprime , 64 bytes

Eu sei que há outra solução Ruby aqui, mas eu não queria fazer comentários com comentários desde que ela foi respondida em 2012 ... e, como se vê, usar um sinalizador de programa conta isso como um idioma diferente , então acho que isso tecnicamente não é "Ruby" de qualquer maneira.

Experimente online!

Explicação

->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←π¨⍳⍵}

teste:

  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 é uma alternativa mais longa (59 caracteres que eu preferiria)

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

teste:

  h 1000000
209867