素数とは何ですか?
あ 素数 より大きい自然数として定義されます 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
- ゴールドバッハ予想のプログラム
- 素数とフィボナッチ
- 合成数
- 素数に関する最近の記事!