introduction

La fonction de comptage de nombres premiers , également connue sous le nom de fonction Pi , renvoie la quantité de nombres premiers inférieure ou égale à x.$\pi(x)$

Défi

Votre programme prendra un entier x que vous pouvez supposer positif et produira un seul entier égal au nombre de nombres premiers inférieur ou égal à x. Il s'agit d'un défi de code-golf , donc le gagnant sera le programme avec le moins d'octets.

Vous pouvez utiliser n'importe quelle langue de votre choix à condition qu'elle existait avant que ce défi ne soit relevé, mais si la langue a une fonction de comptage de prime intégrée ou une fonction de vérification de primalité (telle que Mathematica), cette fonction ne peut pas être utilisée dans votre code .

Exemples d'entrées

Entrée:
1
Sortie:
0

Entrée:
2
Sortie:
1

Entrée:
5
Sortie:
3

A000720 - OEIS

05AB1E , 3 octets

!fg

Cela suppose que les fonctions intégrées de factorisation sont autorisées. Essayez-le en ligne!

Comment ça marche

!    Compute the factorial of the input.
 f   Determine its unique prime factors.
  g  Get the length of the resulting list.

Python 2, 45 octets

f=lambda n,k=1,p=1:n/k and p%k+f(n,k+1,p*k*k)

Utilise le générateur principal du théorème de Wilson . Le produit psuit (k-1)!^2, et p%kest 1 pour les nombres premiers et 0 pour les nonprimes.

MATL , 11, 10, 8 , 5 octets

:pYFn

Essayez-le en ligne!

J'ai écrit une version qui avait une explication vraiment cool du fonctionnement des matrices MATL:

:YF!s1=1

Mais ce n'est plus pertinent. Consultez l'historique des révisions si vous voulez le voir.

Nouvelle explication:

:p      % Compute factorial(input)
  YF    % Get the exponenents of prime factorization
    n   % Get the length of the array

Trois octets économisés grâce à la solution géniale de Dennis

Gelée , 8 5 octets

3 octets économisés grâce à @Dennis!

RÆESL

Essayez-le en ligne!

Port de la réponse MATL de DJMcMayhem (ancienne version) affinée par Dennis.

R          Range of input argument
 ÆE        List of lists of exponents of prime-factor decomposition
   S       Vectorized sum. This right-pads inner lists with zeros
    L      Length of result

Modèles MediaWiki avec ParserFunctions , 220 + 19 = 239 octets

{{#ifexpr:{{{2}}}+1={{{1}}}|0|{{#ifexpr:{{{3}}}={{{2}}}|{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{#ifexpr:{{{2}}} mod {{{3}}}=0|{{#expr:1+{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}}+1}}}}}}}}}}}}

Pour appeler le modèle:

{{{P|{{{n}}}|2|2}}}

Arrangé dans le style Lisp:

{{#ifexpr:{{{2}}} + 1 = {{{1}}}|0|
    {{#ifexpr:{{{3}}} = {{{2}}} |
        {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
            {{#ifexpr:{{{2}}} mod {{{3}}} = 0 |
                {{#expr:1 + {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
                {{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}} + 1}}}}}}}}}}}}

Juste un test de primalité basique de 2 à n . Les nombres avec trois accolades autour d'eux sont les variables, où {{{1}}}est n , {{{2}}}est le nombre testé, {{{3}}}est le facteur à vérifier.

Perl, 33 octets

Comprend +1 pour -p

Donnez le numéro d'entrée sur STDIN

primecount.pl

#!/usr/bin/perl -p
$_=1x$_;$_=s%(?!(11+)\1+$)%%eg-2

Donne le mauvais résultat 0mais c'est OK, l'op a demandé le support des entiers positifs uniquement.

Rétine, 31 octets

Le nombre d'octets suppose un codage ISO 8859-1. Convertissez l'entrée en unaire, générez la plage de 1à n, chacune sur sa propre ligne. Faites correspondre les nombres premiers.

.*
$*
\B
¶$`
m`^(?!(..+)\1+$)..

Essayez-le en ligne - L'entrée est beaucoup plus grande que 2800 soit expire soit manque de mémoire.

Les références:

Générateur de gamme Martin

Premier vérificateur de Martin

Gelée , 3 octets

!Æv

Essayez-le en ligne!

Comment ça marche

!Æv  Main link. Argument: n

!    Compute the factorial of n.
 Æv  Count the number of distinct prime factors.

Gelée , 13 11 10 9 8 7 6 octets

Utiliser aucune fonction principale intégrée de quelque
nature que ce soit -1 octet grâce à @miles (utiliser une table)
-1 octet grâce à @Dennis (convertir de unaire pour compter les diviseurs)

ḍþḅ1ċ2

TryItOnline
Ou consultez les 100 premiers termes de la sérien=[1,100], également sur TryItOnline

Comment?

ḍþḅ1ċ2 - Main link: n
 þ     - table or outer product, n implicitly becomes [1,2,3,...n]
ḍ      - divides
  ḅ1   - Convert from unary: number of numbers in [1,2,3,...,n] that divide x
                             (numbers greater than x do not divide x)
    ċ2 - count 2s: count the numbers in [1,2,3,...,n] with exactly 2 divisors
                   (only primes have 2 divisors: 1 and themselves)

JavaScript (ES6), 45 43 octets

f=(n,x=n)=>n>1&&(--x<2)+(n%x?f(n,x):f(n-1))

Une modification de ma fonction de primalité 36 35 33 octets (1 octet enregistré par @Neil, 2 par @Arnauld):

f=(n,x=n)=>n>1&--x<2||n%x&&f(n,x)

(Je ne peux pas poster ceci n'importe où parce que ce nombre est un nombre premier? Accepte uniquement les programmes complets ...)

Extrait de test

f=(n,x=n)=>n>1&&(--x<2)+(n%x?f(n,x):f(n-1))

<input type="number" oninput="console.log('f('+this.value+') is '+f(this.value))" value=2>

PowerShell v2 +, 98 octets

param($n)if($j='001'[$n]){}else{for($i=1;$i-lt$n){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$j++}}}$j

Attention: Ceci est lent pour une entrée volumineuse.

Fondamentalement, la recherche unaire de Is this number a prime? , couplé à une forboucle et un $j++compteur. Un peu de logique supplémentaire sur le devant pour tenir compte de l'entrée des cas de bord 1et 2, en raison de la façon dont le clôtureposting fonctionne dans les forboucles.

05AB1E , 5 octets

Suppose que les fonctions intégrées de factorisation principale sont autorisées.

Code:

LÒ1ùg

Explication:

L      # Get the range [1, ..., input]
 Ò     # Prime factorize each with duplicates
  1ù   # Keep the elements with length 1
    g  # Get the length of the resulting array

Utilise l' encodage CP-1252 . Essayez-le en ligne!

CJam , 7 octets

rim!mF,

Essayez-le en ligne! Utilise une fonction de factorisation.

Explication:

ri      | read input as integer
  m!    | take the factorial
    mF  | factorize with exponents (one element per prime)
      , | find length

Gelée , 6 octets

Ḷ!²%RS

Cela utilise uniquement l'arithmétique de base et le théorème de Wilson. Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça marche

Ḷ!²%RS  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n - 1].
 !      Factorial; yield [0!, ..., (n - 1)!].
  ²     Square; yield [0!², ..., (n - 1)!²].
    R   Range; yield [1, ..., n].
   %    Modulus; yield [0!² % 1, ..., (n - 1)!² % n].
        By a corollary to Wilson's theorem, (k - 1)!² % k yields 1 if k is prime
        and 0 if k is 1 or composite.
     S  Sum; add the resulting Booleans.

C # 5.0 78 77

int F(int n){int z=n;if(n<2)return 0;for(;n%--z!=0;);return(2>z?1:0)+F(n-1);}

Non golfé

int F(int n)
{
    var z = n;
    if (n < 2) return 0;
    for (; n % --z != 0;) ;
    return F(n - 1) + (2 > z ? 1 : 0);
}

Pyth - 7 6 octets

Puisque d'autres utilisent des fonctions de factorisation principales ...

l{sPMS

Suite de tests .

Bash + coreutils, 30

seq $1|factor|egrep -c :.\\S+$

Ideone.

Pack Bash + coreutils + BSD-games, 22

primes 1 $[$1+1]|wc -l

Cette réponse plus courte exige que vous avez le paquet bsdgames installé: sudo apt install bsdgames.

Pyke, 8 6 octets

SmPs}l

Essayez-le ici!

Merci à Maltysen pour le nouvel algorithme

SmP    -    map(factorise, input)
   s   -   sum(^)
    }  -  uniquify(^)
     l - len(^)

C #, 157 octets

n=>{int c=0,i=1,j;bool f;for(;i<=n;i++){if(i==1);else if(i<=3)c++;else if(i%2==0|i%3==0);else{j=5;f=1>0;while(j*j<=i)if(i%j++==0)f=1<0;c+=f?1:0;}}return c;};

Programme complet avec cas de test:

using System;

class a
{
    static void Main()
    {
        Func<int, int> s = n =>
            {
                int c = 0, i = 1, j;
                bool f;
                for (; i <= n; i++)
                {
                    if (i == 1) ;
                    else if (i <= 3) c++;
                    else if (i % 2 == 0 | i % 3 == 0) ;
                    else
                    {
                        j = 5;
                        f = 1 > 0;
                        while (j * j <= i)
                            if (i % j++ == 0)
                                f = 1 < 0;
                        c += f ? 1 : 0;
                    }
                }
                return c;
            };

        Console.WriteLine("1 -> 0 : " + (s(1) == 0 ? "OK" : "FAIL"));
        Console.WriteLine("2 -> 1 : " + (s(2) == 1 ? "OK" : "FAIL"));
        Console.WriteLine("5 -> 3 : " + (s(5) == 3 ? "OK" : "FAIL"));
        Console.WriteLine("10 -> 4 : " + (s(10) == 4 ? "OK" : "FAIL"));
        Console.WriteLine("100 -> 25 : " + (s(100) == 25 ? "OK" : "FAIL"));
        Console.WriteLine("1,000 -> 168 : " + (s(1000) == 168 ? "OK" : "FAIL"));
        Console.WriteLine("10,000 -> 1,229 : " + (s(10000) == 1229 ? "OK" : "FAIL"));
        Console.WriteLine("100,000 -> 9,592 : " + (s(100000) == 9592 ? "OK" : "FAIL"));
        Console.WriteLine("1,000,000 -> 78,498 : " + (s(1000000) == 78498 ? "OK" : "FAIL"));
    }
}

Commence à prendre un certain temps une fois que vous avez dépassé le million.

Matlab, 60 octets

Poursuivant mon attachement aux fonctions Matlab à une ligne. Sans utiliser une factorisation intégrée:

f=@(x) nnz(arrayfun(@(x) x-2==nnz(mod(x,[1:1:x])),[1:1:x]));

Étant donné qu'un nombre premier yn'a que deux facteurs [1,y]: nous comptons les nombres dans la plage [1,x]qui n'ont que deux facteurs.

L'utilisation de la factorisation permet un raccourcissement important (jusqu'à 46 octets).

g=@(x) size(unique(factor(factorial(x))),2);

Conclusion: Besoin de se pencher sur les langues de golf: D

En fait, 10 octets

C'était la solution la plus courte que j'ai trouvée qui ne rencontrait pas de bugs d'interprétation sur TIO. Suggestions de golf bienvenues. Essayez-le en ligne!

;╗r`P╜>`░l

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
r        Push range [0..(n-1)].
`...`░   Push values of the range where the following function returns a truthy value.
  P        Push the a-th prime
  ╜        Push n from register 0.
  >        Check if n > the a-th prime.
l        Push len(the_resulting_list).
         Implicit return.

Gelée , 3 octets

ÆRL

Jelly a une fonction de comptage de prime intégrée ÆCet une fonction de vérification de prime ÆP, cela utilise à la place une fonction de génération de prime intégrée ÆRet prend la longueur L.

Je suppose que cela est à peu près aussi limite que l'utilisation des facteurs intégrés de factorisation principale, qui prendraient également 3 octets avec !Æv( !factorielle, Ævcompte les facteurs premiers)

PHP, 96 92 octets

for($j=$argv[1]-1;$j>0;$j--){$p=1;for($i=2;$i<$j;$i++)if(is_int($j/$i))$p=0;$t+=$p;}echo $t;

4 octets enregistrés grâce à Roman Gräf

Testez en ligne

Code de test non golfé:

$argv[1] = 5;

for($j=$argv[1]-1;$j>0;$j--) {
    $p=1;
    for($i=2;$i<$j;$i++) {
        if(is_int($j/$i)) {
            $p=0;
        }
    }
    $t+=$p;
}
echo $t;

Testez en ligne

APL (Dyalog Unicode) , 13 octets ^SBCS

2+.=0+.=⍳∘.|⍳

Essayez-le en ligne!

⍳ ɩ ndices 1…
 N⧽ ∘.| table de reste (en utilisant ces deux comme axes)
⍳ ɩ ndices 1… N

0+.= la somme des éléments égale à zéro (c'est-à-dire combien de diviseurs chacun a)

2+.= la somme des éléments égale à deux (ie combien de nombres premiers y a-t-il)

Python 3, 40 octets

f=lambda n:1if n<1else(2**n%n==2)+f(n-1)

Un entier impair k est premier si an seulement si 2 ** (k-1) est congru à 1 mod k. Ainsi, nous vérifions simplement cette condition et ajoutons 1 pour le cas de k = 2.

MATL , 9 octets

Cela évite la décomposition en facteur premier. Sa complexité est O ( n ²).

:t!\~s2=s

Essayez-le en ligne!

:     % Range [1 2 ... n] (row vector)
t!    % Duplicate and transpose into a column vector
\     % Modulo with broadcast. Gives matrix in which entry (i,j) is i modulo j, with
      % i, j in [1 2 ... n]. A value 0 in entry (i,j) means i is divisible by j
~     % Negate. Now 1 means i is divisible by j
s     % Sum of each column. Gives row vector with the number of divisors of each j
2=    % Compare each entry with 2. A true result corresponds to a prime
s     % Sum

JavaScript (ES6), 50 + 2 46 + 2 43 octets

Enregistré 3 5 octets grâce à Neil:

f=n=>n&&eval(`for(z=n;n%--z;);1==z`)+f(n-1)

evalpeut accéder au nparamètre.
Le eval(...)vérifie si nest premier.

Solutions précédentes: le
nombre d'octets devrait être +2 car j'ai oublié de nommer la fonction f=(nécessaire pour la récursivité)

46 + 2 octets (économisés 3 octets grâce aux productions ETH):

n=>n&&eval(`for(z=n=${n};n%--z;);1==z`)+f(n-1)

50 + 2 octets:

n=>n&&eval(`for(z=${n};${n}%--z&&z;);1==z`)+f(n-1)

Java 7,102 octets

Force brute

int f(int n){int i=2,j=2,c=1,t=0;for(;i<=n;j=2,c+=t==1?1:0,i++)for(;j<i;t=i%j++==0?j=i+1:1);return c;}

Non golfé

int f(int n){
int i=2,j=2,c=1,t=0;
for(;i<=n;j=2,c+=t==1?1:0,i++)
    for(;j<i;)
        t=i%j++==0?j=i+1:1;
    return c;
 }

q 35 octets

{sum 1=sum'[0=2_' a mod\: a:til x]}

En fait, 10 octets

Si ma première réponse Actually n'est pas autorisée pour l'utilisation d'une fonction génératrice de nombres premiers, voici une réponse de secours utilisant le théorème de Wilson. Suggestions de golf bienvenues. Essayez-le en ligne!

R`;D!²%`MΣ

Essayez-le en ligne

         Implicit input n.
R        Push range [1..n]
`...`M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  D        Decrement one of the copies of k.
  !²       Push ((k-1)!)².
  %        Push ((k-1)!)² % k. This returns 1 if k is prime, else 0.
Σ        Sums the result of the map, adding all the 1s that represent primes, 
          giving the total number of primes less than n.
         Implicit return.