logo

TechCodeview

소수

소수란 무엇입니까?

ㅏ 소수 보다 큰 자연수로 정의된다. 1 1과 자기 자신으로만 나누어질 수 있습니다.

즉, 소수는 1과 숫자 자체라는 정확히 두 개의 인수를 갖는 1보다 큰 양의 정수입니다. 처음 몇 개의 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23 입니다. . .



메모: 1은 소수도 아니고 합성수도 아니다. 1을 제외한 나머지 수는 소수와 합성수로 분류됩니다.

소수

소수에 관한 몇 가지 흥미로운 사실:

  • 가장 작은 2를 제외하고 소수 유일한 짝수인 소수는 모두 홀수입니다.
  • 모든 소수는 다음과 같은 형태로 표현될 수 있습니다. 6n + 1 또는 6n - 1 소수를 제외한 2 그리고 삼 , 여기서 n은 임의의 자연수입니다.
  • 2와 3 연속된 두 자연수만이 소수이다.
  • 골드바흐의 추측: 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있습니다.
  • 윌슨 정리 : 윌슨의 정리는 다음과 같은 경우에만 자연수 p> 1이 소수라고 말합니다.

(p – 1) ! p에 대해 -1
또는,
(p – 1) ! ‚ (p-1) 모드 p



ㅏn-1‚ 1 (mod n)
또는,
ㅏn-1% n = 1

  • 소수 정리 : 무작위로 선택한 주어진 숫자 n이 소수일 확률은 숫자의 자릿수 또는 n의 로그에 반비례합니다.
  • 레무안의 추측 : 5보다 큰 홀수 정수는 홀수 소수(2를 제외한 모든 소수는 홀수임)와 짝수 세미프라임의 합으로 표현될 수 있습니다. 세미소수는 두 소수의 곱입니다. 이것을 르무안의 추측이라고 합니다.

소수의 속성:

  • 1보다 큰 모든 숫자는 적어도 하나의 소수로 나눌 수 있습니다.
  • 2보다 큰 모든 짝수 양의 정수는 두 소수의 합으로 표현될 수 있습니다.
  • 2를 제외한 다른 소수는 모두 홀수이다. 즉, 2만이 짝수인 유일한 소수라고 할 수 있다.
  • 두 소수는 항상 서로 서로소입니다.
  • 각 합성수는 소인수로 분해될 수 있으며 개별적으로 이들 모두는 본질적으로 고유합니다.

소수 및 공동소수:

다음을 구별하는 것이 중요합니다. 소수 그리고 공동소수 . 아래에는 소수와 공동소수의 차이점이 나와 있습니다.

  • Coprime 수는 항상 쌍으로 간주되는 반면 소수는 단일 수입니다.
  • 공소수(co-prime number)는 1 외에 공통인수가 없는 수입니다. 이에 비해 소수에는 이러한 조건이 없습니다.
  • 공동소수는 소수이거나 합성수일 수 있지만 최대공약수(GCF)는 항상 1이어야 합니다. 합성수와 달리 소수에는 1과 숫자 자체라는 두 가지 인수만 있습니다.
  • 공동 소수의 예: 13 15는 공동소수입니다. 13의 약수는 1과 13이고 15의 약수는 1, 3, 5입니다. 공약수가 1뿐이므로 서로소인 것을 알 수 있습니다.
  • 소수의 예: 소수의 예로는 2, 3, 5, 7, 11 등이 있습니다.

번호가 프라임인지 아닌지 확인하는 방법은 무엇입니까?

순진한 접근 방식: 순진한 접근 방식은



2에서 (n-1)까지 반복하고 이 범위에 나누는 숫자가 있는지 확인합니다. N . 숫자가 나누어지면 N 이면 소수가 아닙니다.

시간 복잡도: 에)
보조 공간: 오(1)

순진한 접근 방식(재귀적): 재귀를 사용하여 2 사이의 숫자가 있는지 확인할 수도 있습니다. 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> 

>

>

파이썬3




# 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# 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 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.> >>

레카 나이 

>

>

산출 

 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> 

>

>

파이썬3




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

>

>

씨#




// 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> 

>

>

자바스크립트

스택 자바




// 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(제곱(n))
보조 공간: 오(1)

또 다른 효율적인 접근 방식: 숫자가 소수인지 확인하려면 아래 아이디어를 따르십시오.

우리는 1, 2, 3과 같은 몇 가지 숫자와 2와 ​​3으로 나누어지는 숫자를 별도의 경우와 나머지 숫자에 대해 다룰 것입니다. 5부터 sqrt(n)까지 반복하고 (해당 값) 또는 (해당 값 + 2)가 n을 나누는지 여부를 각 반복마다 확인하고 값을 6만큼 증가시킵니다. [모든 소수는 6n+1 또는 6n-1로 표현될 수 있기 때문입니다. ]. 나누는 숫자를 찾으면 false를 반환합니다.

위 아이디어를 구현한 내용은 다음과 같습니다.

Ravel은 파이썬에서 무엇을 하나요?

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> 

>

>

씨




// 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> 

>

>

파이썬3




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# 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)> 

>

>

자바스크립트




// 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(제곱(n))
보조 공간: 오(1)

효율적인 솔루션

  • 소수성 테스트 | 세트 1(개론 및 수업방법)
  • 소수성 테스트 | 세트 2(페르마법)
  • 소수성 테스트 | 세트 3(밀러-라빈)
  • 소수성 테스트 | 세트 4(솔로바이-스트라센)
  • 루카스 원시성 테스트

N보다 작은 모든 소수를 찾는 알고리즘

  • 에라토스테네스의 체
  • 0(n) 시간복잡도의 에라토스테네스의 체
  • 분할된 체
  • 순다람의 체
  • 비트와이즈 체
  • Sieve에 대한 최근 기사!

소수와 관련된 추가 문제

  • 두 개의 서로 다른 소수를 찾으십시오. ㅏ 주어진 제품
  • N보다 작거나 같은 모든 소수를 인쇄합니다.
  • 소수에 대한 재귀 프로그램
  • 두 개의 소수를 찾으십시오. ㅏ 주어진 금액
  • 범위 내 소수에서 가장 높은 숫자 찾기
  • 다중 쿼리에 Sieve O(log n)을 사용한 소인수 분해
  • 주어진 숫자의 모든 소인수를 출력하는 프로그램
  • n까지의 최소 소인수
  • 배열 요소의 LCM 주요 요소 – techcodeview.com
  • 골드바흐의 추측을 위한 프로그램
  • 소수와 피보나치
  • 합성 수
  • 소수에 관한 최근 기사!