Einführung

Die Primzahlfunktion , die auch als Pi-Funktion , gibt die Anzahl der Primzahlen kleiner oder gleich x zurück.$\pi(x)$

Herausforderung

Ihr Programm verwendet eine Ganzzahl x, die Sie als positiv annehmen können, und gibt eine einzelne Ganzzahl aus, die der Anzahl der Primzahlen kleiner oder gleich x entspricht. Dies ist eine Code-Golf- Herausforderung, daher wird der Gewinner das Programm mit den wenigsten Bytes sein.

Sie können eine beliebige Sprache Ihrer Wahl verwenden, sofern diese vor Beginn dieser Herausforderung vorhanden war. Wenn die Sprache jedoch über eine integrierte Primzahlfunktion oder eine Primalitätsprüffunktion (z. B. Mathematica) verfügt, kann diese Funktion in Ihrem Code nicht verwendet werden .

Beispieleingaben

Eingabe:
1
Ausgabe:
0

Eingabe:
2
Ausgabe:
1

Eingabe:
5
Ausgabe:
3

A000720 - OEIS

05AB1E , 3 Bytes

!fg

Dies setzt voraus, dass eingebaute Faktorisierungsfunktionen zulässig sind. Probieren Sie es online!

Wie es funktioniert

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

Python 2, 45 Bytes

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

Verwendet den Wilson's Theorem Prime Generator. Das Produkt pverfolgt (k-1)!^2und p%kist 1 für Primzahlen und 0 für Nicht-Primzahlen.

MATL , 11, 10, 8 , 5 Bytes

:pYFn

Probieren Sie es online!

Ich habe eine Version geschrieben, die wirklich cool erklärt, wie MATLs Matrizen funktionieren:

:YF!s1=1

Aber es ist nicht mehr relevant. Sehen Sie sich den Revisionsverlauf an, wenn Sie ihn sehen möchten.

Neue Erklärung:

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

Drei Bytes gespart dank Dennis 'genialer Lösung

Gelee , 8 5 Bytes

3 Bytes gespart dank @Dennis!

RÆESL

Probieren Sie es online!

Port von DJMcMayhem's MATL-Antwort (frühere Version), verfeinert von 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

MediaWiki-Vorlagen mit ParserFunctions , 220 + 19 = 239 Byte

{{#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}}}}}}}}}}}}

So rufen Sie die Vorlage auf:

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

Arrangiert im Lisp-Stil:

{{#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}}}}}}}}}}}}

Nur ein einfacher Primalitätstest von 2 bis n . Die Zahlen mit drei Klammern um ihnen die Variablen sind, wo {{{1}}}ist n , {{{2}}}ist die Zahl, getestet wird , {{{3}}}ist der Faktor zu überprüfen.

Perl, 33 Bytes

Beinhaltet +1 für -p

Geben Sie die Eingangsnummer bei STDIN ein

primecount.pl

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

Gibt das falsche Ergebnis für an, 0aber das ist in Ordnung, die Operation bat nur um Unterstützung für positive ganze Zahlen.

Retina, 31 Bytes

Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus. Konvertieren Sie die Eingabe in unär, und generieren Sie den Bereich von 1bis für njede Zeile. Bringe die Primzahlen zusammen.

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

Probieren Sie es online aus - Eingabe viel größer als 2800, entweder zeitlich begrenzt oder nicht genügend Arbeitsspeicher.

Verweise:

Martins Entfernungsmesser

Martins Prime Checker

Gelee , 3 Bytes

!Æv

Probieren Sie es online!

Wie es funktioniert

!Æv  Main link. Argument: n

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

Jelly , 13 11 10 9 8 7 6 Bytes

Keine eingebauten Prim-Funktionen verwenden
-1 Byte dank @miles (eine Tabelle verwenden)
-1 Byte dank @Dennis (von unary konvertieren, um die Divisoren hochzuzählen)

ḍþḅ1ċ2

TryItOnline
Oder sehen Sie sich die ersten 100 Begriffe der Reihe ann=[1,100], auch bei TryItOnline

Wie?

ḍþḅ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 Byte

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

Eine Modifikation meiner 36 35 33-Byte-Primalitätsfunktion (1 Byte gespeichert von @Neil, 2 von @Arnauld):

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

(Ich kann das nirgendwo posten, weil Ist diese Nummer eine Primzahl? Akzeptiert nur vollständige Programme ...)

Testschnipsel

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 Byte

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

Achtung: Dies ist bei großen Eingaben langsam .

Grundsätzlich die unary-basierte Suche von Ist diese Zahl eine Primzahl? , gekoppelt mit einer forSchleife und einem $j++Zähler. Ein wenig zusätzliche Logik auf der Vorderseite, um die Eingabe von Kantenfällen zu berücksichtigen 1und 2aufgrund der Funktionsweise der Zaunpfosten in den forSchleifen.

05AB1E , 5 Bytes

Nimmt an, dass eingebaute Primfaktoren zulässig sind.

Code:

LÒ1ùg

Erläuterung:

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

Verwendet die CP-1252- Codierung. Probieren Sie es online!

CJam , 7 Bytes

rim!mF,

Probieren Sie es online! Verwendet eine Faktorisierungsfunktion.

Erläuterung:

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

Gelee , 6 Bytes

Ḷ!²%RS

Hierbei werden nur die Grundrechenarten und der Satz von Wilson verwendet. Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Ḷ!²%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);}

Ungolfed

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 Bytes

Da andere Primfaktorisierungsfunktionen verwenden ...

l{sPMS

Test Suite .

Bash + Coreutils, 30

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

Ideone.

Bash + Coreutils + BSD-Spielepaket, 22

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

Diese kürzere Antwort erfordert , dass Sie das bsdgames Paket installiert sein : sudo apt install bsdgames.

Pyke, 8 6 Bytes

SmPs}l

Probieren Sie es hier aus!

Vielen Dank an Maltysen für den neuen Algorithmus

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

C #, 157 Bytes

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

Volles Programm mit Testfällen:

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"));
    }
}

Beginnt eine Weile zu dauern, sobald Sie über 1 Million gehen.

Matlab, 60 Bytes

Fortsetzung meiner Einstellung zu einzeiligen Matlab-Funktionen. Ohne eingebaute Faktorisierung:

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

Vorausgesetzt, eine Primzahl yhat nur zwei Faktoren [1,y]: Wir zählen die Zahlen im Bereich [1,x], die nur zwei Faktoren haben.

Die Verwendung der Faktorisierung ermöglicht eine signifikante Verkürzung (bis zu 46 Byte).

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

Fazit: Müssen in sie Golf Sprachen suchen: D

Eigentlich 10 Bytes

Dies war die kürzeste Lösung, die ich gefunden habe und die bei TIO nicht auf Interpreter-Bugs gestoßen ist. Golfvorschläge sind willkommen. Probieren Sie es online!

;╗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.

Gelee , 3 Bytes

ÆRL

Jelly hat eine eingebaute Funktion zum Zählen von Primzahlen ÆCund eine Funktion zum Prüfen von Primzahlen. ÆPStattdessen wird eine eingebaute Funktion zum Erzeugen von Primzahlen verwendet ÆRund die Länge ermittelt L.

Ich denke, dies ist ungefähr so ​​grenzwertig wie die Verwendung von eingebauten Primfaktoren, die auch 3 Bytes mit !Æv( !Fakultät, ÆvPrimfaktoren zählen) benötigen würden.

PHP, 96 92 Bytes

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 Bytes gespart dank Roman Gräf

Online testen

Ungolfed-Testcode:

$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;

Online testen

APL (Dyalog Unicode) , 13 Byte ^SBCS

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

Probieren Sie es online!

⍳ ɩ ndices 1 ... N
 ⧽ ∘.| Rest-Tabelle (die zwei als Achsen verwenden)
⍳  ɩ ndices 1 ... N

0+.= die Summe der Elemente gleich Null (dh wie viele Teiler hat jeder)

2+.= die Summe der Elemente gleich zwei (dh wie viele Primzahlen gibt es)

Python 3, 40 Bytes

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

Eine ungerade ganze Zahl k ist eine Primzahl, wenn nur 2 ** (k - 1) zu 1 mod k kongruent ist. Wir überprüfen also nur diese Bedingung und addieren 1 für den Fall von k = 2.

MATL , 9 Bytes

Dies vermeidet eine Zersetzung des Primfaktors. Seine Komplexität ist O ( n ²).

:t!\~s2=s

Probieren Sie es online!

:     % 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 Bytes

3 5 Bytes gespart dank Neil:

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

evalkann auf den nParameter zugreifen .
Das eval(...)prüft, ob nPrime ist.

Vorherige Lösungen: Die
Byteanzahl sollte +2 sein, da ich vergessen habe, die Funktion zu benennen f=(für die Rekursion erforderlich)

46 + 2 Bytes (3 Bytes dank ETHproductions eingespart):

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

50 + 2 Bytes:

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

Java 7.102 Bytes

Rohe Gewalt

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

Ungolfed

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 Bytes

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

Eigentlich 10 Bytes

Wenn für meine erste tatsächliche Antwort die Verwendung einer Funktion zur Erzeugung von Primzahlen nicht zulässig ist, ist hier eine Ersatzantwort unter Verwendung des Wilson-Theorems. Golfvorschläge sind willkommen. Probieren Sie es online!

R`;D!²%`MΣ

Probieren Sie es online aus

         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.