PRIEMGETALLEN - TECHCODEVIEW.COM

Wat zijn priemgetallen?

A priemgetal wordt gedefinieerd als een natuurlijk getal groter dan 1 en is deelbaar door slechts 1 en zichzelf.

Met andere woorden: het priemgetal is een positief geheel getal groter dan 1 dat precies twee factoren heeft: 1 en het getal zelf. De eerste paar priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23. . .

Opmerking: 1 is niet primair of samengesteld. De overige getallen, behalve 1, worden geclassificeerd als priemgetallen en samengestelde getallen.

priemgetallen

Enkele interessante feiten over priemgetallen:

Behalve 2, dat is de kleinste priemgetal en het enige even priemgetal, alle priemgetallen zijn oneven getallen.
Elk priemgetal kan worden weergegeven in de vorm van 6n + 1 of 6n – 1 behalve de priemgetallen 2 En 3 , waarbij n een natuurlijk getal is.
2 en 3 zijn slechts twee opeenvolgende natuurlijke getallen die priemgetallen zijn.
Goldbach-vermoeden: Elk even geheel getal groter dan 2 kan worden uitgedrukt als de som van twee priemgetallen.
Wilson-stelling : De stelling van Wilson stelt dat een natuurlijk getal p> 1 een priemgetal is dan en slechts dan als

(p – 1) ! ≡ -1 tegen p
OF,
(p – 1) ! ≡ (p-1) mod p

De kleine stelling van Fermat : Als n een priemgetal is, dan is voor elke a, 1 ≤ a

A^n-1≡ 1 (mod n)
OF,
A^n-1% n = 1

Priemgetalstelling : De kans dat een gegeven, willekeurig gekozen getal n een priemgetal is, is omgekeerd evenredig met het aantal cijfers ervan, of met de logaritme van n.
Het vermoeden van Lemoine : Elk oneven geheel getal groter dan 5 kan worden uitgedrukt als de som van een oneven priemgetal (alle priemgetallen behalve 2 zijn oneven) en een even semipriemgetal. Een semipriemgetal is een product van twee priemgetallen. Dit wordt het vermoeden van Lemoine genoemd.

Eigenschappen van priemgetallen:

Elk getal groter dan 1 kan gedeeld worden door minstens één priemgetal.
Elk even positief geheel getal groter dan 2 kan worden uitgedrukt als de som van twee priemgetallen.
Behalve 2 zijn alle andere priemgetallen oneven. Met andere woorden, we kunnen zeggen dat 2 het enige even priemgetal is.
Twee priemgetallen zijn altijd coprime ten opzichte van elkaar.
Elk samengesteld getal kan worden omgezet in priemfactoren en deze zijn individueel allemaal uniek van aard.

Priemgetallen en co-priemgetallen:

Het is belangrijk om onderscheid te maken tussen priemgetallen En co-priemgetallen . Hieronder vindt u de verschillen tussen priemgetallen en co-priemgetallen.

Coprime-getallen worden altijd als een paar beschouwd, terwijl een priemgetal een enkel getal is.
Co-priemgetallen zijn getallen die geen gemeenschappelijke factor hebben behalve 1. Priemgetallen hebben daarentegen niet zo'n voorwaarde.
Een co-priemgetal kan een priemgetal of een samengesteld getal zijn, maar de grootste gemene deler (GCF) moet altijd 1 zijn. In tegenstelling tot samengestelde getallen hebben priemgetallen slechts twee factoren: 1 en het getal zelf.
Voorbeeld van co-prime: 13 en 15 zijn co-priemgetallen. De factoren van 13 zijn 1 en 13 en de factoren van 15 zijn 1, 3 en 5. We kunnen zien dat ze slechts 1 als gemeenschappelijke deler hebben, daarom zijn het coprime-getallen.
Voorbeeld van prime: Een paar voorbeelden van priemgetallen zijn 2, 3, 5, 7 en 11 enz.

Hoe controleer ik of een getal een priemgetal is of niet?

Naïeve aanpak: De naïeve benadering is om

Herhaal van 2 naar (n-1) en controleer of een getal in dit bereik zich deelt N . Als het getal zich deelt N , dan is het geen priemgetal.

Tijdcomplexiteit: OP)
Hulpruimte: O(1)

Naïeve benadering (recursief): Recursie kan ook worden gebruikt om te controleren of een getal tussen 2 tot n – 1 verdeelt n. Als we een getal vinden dat deelt, retourneren we false.

Hieronder ziet u de implementatie van het bovenstaande idee:

C++

// C++ program to check whether a number> // is prime or not using recursion> #include> using> namespace> std;> > // function check whether a number> // is prime or not> bool> isPrime(>int> n)> {> >static> int> i = 2;> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> }> > // Driver Code> int> main()> {> > >isPrime(35) ? cout <<>

' true
'>

: cout <<>

' false
'>

;> >return> 0;> }> > // This code is contributed by yashbeersingh42>

Java

// Java program to check whether a number> // is prime or not using recursion> import> java.io.*;> > class> GFG {> > >static> int> i =>2>;> > >// Function check whether a number> >// is prime or not> >public> static> boolean> isPrime(>int> n)> >{> > >// Corner cases> >if> (n ==>0> || n ==>1>) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// Base cases> >if> (n % i ==>0>) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>35>)) {> >System.out.println(>'true'>);> >}> >else> {> >System.out.println(>'false'>);> >}> >}> }> > // This code is contributed by divyeshrabadiya07>

Python3

# Python3 program to check whether a number> # is prime or not using recursion> > # Function check whether a number> # is prime or not> > > def> isPrime(n, i):> > ># Corner cases> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> False> > ># Checking Prime> >if> (n>=>=> i):> >return> True> > ># Base cases> >if> (n>%> i>=>=> 0>):> >return> False> > >i>+>=> 1> > >return> isPrime(n, i)> > > # Driver Code> if> (isPrime(>35>,>2>)):> >print>(>'true'>)> else>:> >print>(>'false'>)> > # This code is contributed by bunnyram19>

C#

// C# program to check whether a number> // is prime or not using recursion> using> System;> class> GFG {> > >static> int> i = 2;> > >// function check whether a number> >// is prime or not> >static> bool> isPrime(>int> n)> >{> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)> >return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >static> void> Main()> >{> >if> (isPrime(35)) {> >Console.WriteLine(>'true'>);> >}> >else> {> >Console.WriteLine(>'false'>);> >}> >}> }> > // This code is contributed by divyesh072019>

Javascript

> >// JavaScript program to check whether a number> >// is prime or not using recursion> > >// function check whether a number> >// is prime or not> >var> i = 2;> > >function> isPrime(n) {> > >// corner cases> >if> (n == 0 || n == 1) {> >return> false>;> >}> > >// Checking Prime> >if> (n == i)>return> true>;> > >// base cases> >if> (n % i == 0) {> >return> false>;> >}> >i++;> >return> isPrime(n);> >}> > >// Driver Code> > >isPrime(35) ? document.write(>

' true
'>

) : document.write(>

' false
'>

);> > >// This code is contributed by rdtank.> >>

converteer strin naar int

Uitvoer

 false>

Tijdcomplexiteit: OP)
Hulpruimte: O(N) als we de recursiestapel beschouwen. Anders is het O(1).

Efficiënte aanpak: Een efficiënte oplossing is om:

Doorloop alle getallen vanaf 2 naar svierkantswortel van N en controleer voor elk getal of het n deelt [want als een getal wordt uitgedrukt als n = xy en elk van de x of y is groter dan de wortel van n, de andere moet kleiner zijn dan de wortelwaarde]. Als we een getal vinden dat deelt, retourneren we false.

Hieronder vindt u de implementatie:

C++14

// A school method based C++ program to> // check if a number is prime> #include> using> namespace> std;> > // Function check whether a number> // is prime or not> bool> isPrime(>int> n)> {> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to square root of n> >for> (>int> i = 2; i <=>sqrt>(n); i++)> >if> (n % i == 0)> >return> false>;> > >return> true>;> }> > // Driver Code> int> main()> {> >isPrime(11) ? cout <<>

'true
'>

: cout <<>

'false
'>

;> >return> 0;> }>

Java

// A school method based Java program to> // check if a number is prime> import> java.lang.*;> import> java.util.*;> > class> GFG {> > >// Check for number prime or not> >static> boolean> isPrime(>int> n)> >{> > >// Check if number is less than> >// equal to 1> >if> (n <=>1>)> >return> false>;> > >// Check if number is 2> >else> if> (n ==>2>)> >return> true>;> > >// Check if n is a multiple of 2> >else> if> (n %>2> ==>0>)> >return> false>;> > >// If not, then just check the odds> >for> (>int> i =>3>; i <= Math.sqrt(n); i +=>2>) {> >if> (n % i ==>0>)> >return> false>;> >}> >return> true>;> >}> > >// Driver code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>19>))> >System.out.println(>'true'>);> > >else> >System.out.println(>'false'>);> >}> }> > // This code is contributed by Ronak Bhensdadia>

Python3

# A school method based Python3 program> # to check if a number is prime> > > # import sqrt from math module> from> math>import> sqrt> > > > # Function check whether a number> # is prime or not> def> isPrime(n):> > ># Corner case> >if> (n <>=> 1>):> >return> False> > ># Check from 2 to sqrt(n)> >for> i>in> range>(>2>,>int>(sqrt(n))>+>1>):> >if> (n>%> i>=>=> 0>):> >return> False> > >return> True> > > # Driver Code> if> __name__>=>=> '__main__'>:> >if> isPrime(>11>):> >print>(>'true'>)> >else>:> >print>(>'false'>)> > # This code is contributed by Sachin Bisht>

C#

// A school method based C# program to> // check if a number is prime> using> System;> > class> GFG {> > >// Function check whether a> >// number is prime or not> >static> bool> isPrime(>int> n)> >{> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to sqrt(n)> >for> (>int> i = 2; i <= Math.Sqrt(n); i++)> >if> (n % i == 0)> >return> false>;> > >return> true>;> >}> > >// Driver Code> >static> void> Main()> >{> >if> (isPrime(11))> >Console.Write(>'true'>);> > >else> >Console.Write(>'false'>);> >}> }> > // This code is contributed by Sam007>

Javascript

wanneer werd de eerste computer uitgevonden

// A school method based Javascript program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> {> >// Corner case> >if> (n <= 1)> >return> false>;> > >// Check from 2 to n-1> >for>

(let i = 2; i   if (n % i == 0)   return false;     return true;  }    // Driver Code     isPrime(11) ? console.log(' true') : console.log(' false');    // This code is contributed by Mayank Tyagi>

PHP

 // A school method based PHP program to  // check if a number is prime    // Function check whether a number  // is prime or not  function isPrime($n)  {   // Corner case   if ($n <= 1)   return false;     // Check from 2 to n-1   for ($i = 2; $i <$n; $i++)   if ($n % $i == 0)   return false;     return true;  }    // Driver Code  if(isPrime(11))   echo('true');  else  echo('false');    // This code is contributed by Ajit.  ?>>

Uitvoer

true>

Tijdcomplexiteit: O(sqrt(n))
Hulpruimte: O(1)

Nog een efficiënte aanpak: Volg het onderstaande idee om te controleren of het getal een priemgetal is of niet:

We zullen een paar getallen behandelen, zoals 1, 2, 3, en de getallen die deelbaar zijn door 2 en 3 in afzonderlijke gevallen en voor de overige getallen. Itereer van 5 naar sqrt(n) en controleer voor elke iteratie of (die waarde) of (die waarde + 2) n deelt of niet en verhoog de waarde met 6 [omdat elk priemgetal kan worden uitgedrukt als 6n+1 of 6n-1 ]. Als we een getal vinden dat deelt, retourneren we false.

Hieronder vindt u de implementatie van het bovenstaande idee:

C++

'true
'>

: cout <<>

'false
'>

;> >return> 0;> }> // This code is contributed by Suruchi kumari>

C

// A school method based C program to> // check if a number is prime> #include> #include> > // Function check whether a number> // is prime or not> int> isPrime(>int> n)> n % 3 == 0)> >return> 0;> >// Check from 5 to square root of n> >// Iterate i by (i+6)> >for> (>int> i = 5; i * i <= n; i = i + 6)> >if> (n % i == 0> > // Driver Code> int> main()> {> >if> (isPrime(11) == 1)> >printf>(>

'true
'>

);> >else> >printf>(>

'false
'>

);> >return> 0;> }> // This code is contributed by Suruchi Kumari>

Java

// Java program to check whether a number> import> java.lang.*;> import> java.util.*;> > class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> boolean> isPrime(>int> n)> >> >if> (n <=>1>)> >return> false>;> > >// Check if n=2 or n=3> >if> (n ==>2> > > >// Driver Code> >public> static> void> main(String[] args)> >{> >if> (isPrime(>11>)) {> >System.out.println(>'true'>);> >}> >else> {> >System.out.println(>'false'>);> >}> >}> }> > // This code is contributed by Sayan Chatterjee>

Python3

import> math> > def> is_prime(n:>int>)>->>>bool>:> > ># Check if n=1 or n=0> >if> n <>=> 1>:> >return> 'false'> > ># Check if n=2 or n=3> >if> n>=>=> 2> or> n>=>=> 3>:> >return> 'true'> > ># Check whether n is divisible by 2 or 3> >if> n>%> 2> =>=> 0> or> n>%> 3> =>=> 0>:> >return> 'false'> > ># Check from 5 to square root of n> ># Iterate i by (i+6)> >for> i>in> range>(>5>,>int>(math.sqrt(n))>+>1>,>6>):> >if> n>%> i>=>=> 0> or> n>%> (i>+> 2>)>=>=> 0>:> >return> 'false'> > >return> 'true'> > if> __name__>=>=> '__main__'>:> >print>(is_prime(>11>))>

C#

// C# program to check whether a number> using> System;> class> GFG {> > >// Function check whether a number> >// is prime or not> >public> static> bool> isPrime(>int> n)> >> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >if> (isPrime(11)) {> >Console.WriteLine(>'true'>);> >}> >else> {> >Console.WriteLine(>'false'>);> >}> >}> }> > // This code is contributed by Abhijeet> // Kumar(abhijeet_19403)>

Javascript

// A school method based JS program to> // check if a number is prime> > > // Function check whether a number> // is prime or not> function> isPrime(n)> n % (i + 2) == 0)> >return> false>;> > >return> true>;> > > // Driver Code> isPrime(11) ? console.log(>'true'>) : console.log(>'false'>);> > > // This code is contributed by phasing17>

Java Compareto-methode

Uitvoer

true>

Tijdcomplexiteit: O(sqrt(n))
Hulpruimte: O(1)

Efficiënte oplossingen

Primaliteitstest | Set 1 (Introductie en schoolmethode)
Primaliteitstest | Set 2 (Fermat-methode)
Primaliteitstest | Set 3 (Miller-Rabin)
Primaliteitstest | Set 4 (Solovay-Strassen)
Lucas Primaliteitstest

Algoritmen om alle priemgetallen kleiner dan de N te vinden.

Zeef van Eratosthenes
Zeef van Eratosthenes in 0(n) tijdscomplexiteit
Gesegmenteerde zeef
Zeef van Sundaram
Bitsgewijze zeef
Recente artikelen over Zeef!

Meer problemen gerelateerd aan Priemgetal

Vind twee verschillende priemgetallen met A gegeven produkt
Print alle priemgetallen kleiner dan of gelijk aan N
Recursief programma voor priemgetallen
Vind twee priemgetallen met A gegeven som
Vind het hoogst voorkomende cijfer in priemgetallen in een bereik
Prime-factorisatie met behulp van Sieve O(log n) voor meerdere query's
Programma om alle priemfactoren van een bepaald getal af te drukken
Kleinste priemfactor van getallen tot n
Primaire factoren van LCM van array-elementen – techcodeview.com
Programma voor het vermoeden van Goldbach
Priemgetallen en Fibonacci
Samengesteld nummer
Recente artikelen over priemgetallen!