素数とは何ですか?
あ 素数 より大きい自然数として定義されます 1 そしてそれは 1 とそれ自体でのみ割り切れます。
言い換えれば、素数は 1 とその数値自体の 2 つの約数を持つ 1 より大きい正の整数です。最初のいくつかの素数は 2、3、5、7、11、13、17、19、23 です。 。 。
注記： 1 は素数でも合成でもない。 1 を除く残りの数は、素数と合成数に分類されます。
素数
素数に関する興味深い事実:
- 最小の 2 を除く 素数 そして唯一の偶数の素数、すべての素数は奇数です。
- すべての素数は次の形式で表すことができます。 6n+1 または 6n-1 素数を除いて 2 そして 3 ここで、n は任意の自然数です。
- 2と3 素数である連続する 2 つの自然数だけです。
- ゴールドバッハ予想: 2 より大きいすべての偶数整数は、2 つの素数の合計として表現できます。
- ウィルソンの定理 : ウィルソンの定理は、自然数 p> 1 が次の場合にのみ素数であると述べています。
(p – 1) ! ≡ p に対して -1
または、
(p – 1) ! ≡ (p-1) mod p
- フェルマーの小定理 : n が素数の場合、すべての a について、1 ≤ a
あるn-1≡ 1 (mod n)
または、
あるn-1%n = 1
- 素数定理 : ランダムに選択された与えられた数値 n が素数である確率は、その桁数、または n の対数に反比例します。
- ルモインの予想 : 5 より大きい奇数の整数は、奇数の素数 (2 以外のすべての素数は奇数) と偶数の半素数の和として表現できます。半素数は 2 つの素数の積です。これをルモワン予想といいます。
素数の性質:
- 1 より大きいすべての数値は、少なくとも 1 つの素数で割ることができます。
- 2 より大きいすべての偶数の正の整数は、2 つの素数の合計として表現できます。
- 2 を除いて、他のすべての素数は奇数です。つまり、偶数の素数は 2 だけであると言えます。
- 2 つの素数は常に互いに素です。
- 各合成数は素因数に因数分解でき、これらはすべて本質的に一意です。
素数と共素数:
区別することが重要です 素数 そして 共素数 。以下に素数と共素数の違いを示します。
- 素数は単一の数であるのに対し、互いに素な数は常にペアとして考慮されます。
- 共素数とは、1 以外の共通約数を持たない数のことです。一方、素数にはそのような条件がありません。
- 共素数は素数または合成数のいずれかになりますが、その最大公約数 (GCF) は常に 1 である必要があります。合成数とは異なり、素数には 1 とその数値自体の 2 つの因子しかありません。
- 共プライムの例: 13 そして 15 は互いに素です。 13 の約数は 1 と 13、15 の約数は 1、3、5 です。それらの共通約数は 1 だけであることがわかります。したがって、これらは互いに素な数です。
- プライムの例: 素数の例としては、2、3、5、7、11 などがあります。
番号がプライムかどうかを確認するにはどうすればよいですか?
素朴なアプローチ: 素朴なアプローチは、
2 から (n-1) までを繰り返し、この範囲内の数値が割り切れるかどうかを確認します。 n 。数字が割れるなら n 、その場合、それは素数ではありません。
時間計算量: の上）
補助スペース: ○(1)
単純なアプローチ (再帰的): 再帰を使用して、数値が 2 の間であるかどうかを確認することもできます。 to n – 1 は n を除算します。割り算できる数値が見つかった場合は false を返します。
以下は上記のアイデアの実装です。
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 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.> >> |
JavaScriptのforループ
>
>出力
false>
時間計算量: の上）
補助スペース: 再帰スタックを考慮すると O(N) になります。それ以外の場合は、O(1) です。
効率的なアプローチ: 効率的な解決策は次のとおりです。
以下のすべての数値を反復処理します。 2 の平方根 n そして、すべての数値について、それが n を割るかどうかを確認します [数値が次のように表現されている場合 n = xy x または y のいずれかが n のルートより大きく、もう一方がルート値より小さくなければなりません。]割り算できる数値が見つかった場合は false を返します。
以下に実装を示します。
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;> }> |
>
>
ジャワ
// 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
Javaの配列リスト
// 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. ?>>> |
>
>出力
true>
時間計算量: O(sqrt(n))
補助スペース: ○(1)
別の効率的なアプローチ: 数値が素数かどうかを確認するには、次の考え方に従います。
1、2、3などのいくつかの数と、2と3で割り切れる数を場合と残りの数に分けて扱います。 5 から sqrt(n) まで反復し、反復ごとに (その値) または (その値 + 2) が n を除算するかどうかを確認し、値を 6 ずつ増分します (素数は 6n+1 または 6n-1 として表現できるため) ]。割り算できる数値が見つかった場合は false を返します。
以下は、上記のアイデアの実装です。
C++
// 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)> > > // Driver Code> int> main()> {> >isPrime(11) ? cout <<>'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 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)> |
>
アンドロイドを使ったimessageゲーム
>
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> |
>
>出力
true>
時間計算量: O(sqrt(n))
補助スペース: ○(1)
効率的なソリューション
- 素数性テスト |セット 1 (導入とスクール方法)
- 素数性テスト |セット 2 (フェルマー法)
- 素数性テスト |セット 3 (ミラー – ラビン)
- 素数性テスト |セット 4 (ソロヴァイ-シュトラッセン)
- ルーカスの素数性テスト
N より小さいすべての素数を見つけるアルゴリズム。
- エラトステネスのふるい
- 時間計算量 0(n) のエラトステネスのふるい
- 分割ふるい
- スンダラムのふるい
- ビットごとのふるい
- 「ふるい」に関する最近の記事！
素数に関連するその他の問題
- 2 つの異なる素数を見つけるには、 ある 与えられた製品
- N 以下のすべての素数を出力します。
- 素数の再帰プログラム
- 2 つの素数を見つける ある 与えられた合計
- 範囲内の素数の中で最も大きい数字を検索します。
- 複数のクエリに対して Sieve O(log n) を使用した素因数分解
- 指定された数値のすべての素因数を出力するプログラム
- n までの数値の最小素因数
- 配列要素の LCM の素因数 – techcodeview.com
- ゴールドバッハ予想のプログラム
- 素数とフィボナッチ
- 合成数
- 素数に関する最近の記事！