파이썬 언어를위한 isPrime 함수

그래서 인터넷에서 약간의 도움으로이 문제를 해결할 수 있었고 이것이 내가 가진 것입니다.

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True

하지만 내 질문은 정말로 그것을하는 방법이지만, 왜. 나는 1이 "프라임"숫자로 간주되지 않는다는 것을 이해하며, 범위 내에서 어떤 것이 든 나누면 자동으로 프라임을 반환하므로 False 문을 반환한다는 것을 이해합니다. 하지만 제 질문은 여기에 "n"놀이가 어떤 역할을합니까? 관심을 가져 주셔서 대단히 감사합니다.

추신. 나는 매우 미숙하고 한 달 전에 프로그래밍에 소개되었습니다 : S

해결법

==============================
1.인터넷 주변에 떠있는 많은 소수 테스트 중 다음과 같은 주요 테스트를 고려하십시오.

인터넷 주변에 떠있는 많은 소수 테스트 중 다음과 같은 주요 테스트를 고려하십시오.
```
def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    print '\t',f
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True    
```
프라임 번호 5003을 고려하십시오.
```
print is_prime(5003)
```
인쇄물:
```
 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True
```
r = int (n ** 0.5) 라인은 70으로 평가됩니다 (5003의 제곱근은 70.7318881411이고 int ()는이 값을 자릅니다)

최초의 몇 가지 테스트와 루프 중간의 테스트 때문에 루프는 매 6 번째마다 평가하면됩니다.

5005의 다음 홀수 (2 이외의 모든 짝수는 소수가 아니기 때문에)를 생각해보십시오. 똑같은 내용이 출력됩니다.
```
 5
False
```
제한은 x * y == y * x이므로 제곱근입니다.이 함수는 5005가 5로 나눌 수 있으므로 소수가 아닌 것을 알기 위해 1 개의 루프 만 수행하면됩니다. 5 X 1001 == 1001 X 5 (둘 다 5005 임) 이후, 우리는 5에서 우리가 알고있는 것을 알기 위해 루프에서 1001로 완전히 갈 필요가 없습니다!

자, 가지고있는 알고리즘을 살펴 보자.
```
def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True
```
두 가지 문제가 있습니다.

그래서:
```
def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3,int(n**0.5)+1,2):   # only odd numbers
        if n%i==0:
            return False    

    return True
```
확인 - 속도가 약 30 % 빨라졌습니다 (벤치마킹 한 결과 ...)

is_prime을 사용한 알고리즘은 매 6 번째 정수 만 루프를 통해 반복하기 때문에 여전히 약 2 배 빠른 속도입니다. (다시 한 번 벤치마킹했습니다.)

참고 : x ** 0.5는 제곱근입니다.
```
>>> import math
>>> math.sqrt(100)==100**0.5
True
```
참고 2 : 소수 테스트는 컴퓨터 과학에서 흥미로운 문제입니다.
==============================
2.n ** .5에서는 n을 제곱하지 않고 제곱근을 취합니다.

n ** .5에서는 n을 제곱하지 않고 제곱근을 취합니다.

숫자 20을 고려하십시오. 정수 인자는 1, 2, 4, 5, 10 및 20입니다. 20을 2로 나누고 10을 얻으면 확인하지 않고도 10으로 나눌 수 있습니다. 4로 나누고 5를 얻으면 5를 확인하지 않고도 4와 5로 나눌 수 있다는 것을 알 수 있습니다.

요인의 중간 점에 도달 한 후에는 더 이상 이전에 요인으로 인식하지 않은 번호를 확인할 필요가 없습니다. 그러므로 무언가가 소수인지보기 위해 중간에 가면되고,이 중간 점은 숫자의 제곱근을 취함으로써 찾을 수 있습니다.

또한 이유 1은 소수가 아니기 때문에 소수는 2 개의 요인 1과 자체를 갖는 것으로 정의됩니다. 즉 2는 1 * 2, 3은 1 * 3, 5는 1 * 5입니다. 그러나 1 (1 * 1)은 오직 하나의 요소 만 가지고 있습니다. 따라서이 정의를 충족하지 못합니다.
==============================
3.질문은 조금 전에 묻지 만, 나는 당신을위한 더 짧은 해결책을 가지고있다.

질문은 조금 전에 묻지 만, 나는 당신을위한 더 짧은 해결책을 가지고있다.
```
isPrime(Number):
    return 2 in [Number,2**Number%Number]
```
숫자 연산이 2가 아닌 소수라면 2를 반환합니다. 그러나 2가 주어진 숫자이면 우리가 찾고있는 목록에 추가됩니다.
```
2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2
```
등등 ...

isPrime ()은 Number가 Prime이면 True를 반환하고 그렇지 않으면 False를 반환합니다.
==============================
4.부동 소수점 연산은 아래에서 수행되지 않습니다. 이것은 더 빠르며 더 높은 논증을 용인 할 것입니다. 당신이 제곱근에만 가야만하는 이유는 숫자의 제곱근보다 큰 인수가 있다면 그 인수도 제곱근보다 작기 때문입니다.

부동 소수점 연산은 아래에서 수행되지 않습니다. 이것은 더 빠르며 더 높은 논증을 용인 할 것입니다. 당신이 제곱근에만 가야만하는 이유는 숫자의 제곱근보다 큰 인수가 있다면 그 인수도 제곱근보다 작기 때문입니다.
```
def is_prime(n):
    """"pre-condition: n is a nonnegative integer
    post-condition: return True if n is prime and False otherwise."""
    if n < 2: 
         return False;
    if n % 2 == 0:             
         return n == 2  # return False
    k = 3
    while k*k <= n:
         if n % k == 0:
             return False
         k += 2
    return True
```
==============================
5.숫자의 제곱근을 찾는 것이 효율성을위한 것입니다. 예. 36의 요인을 찾으려한다면 36을 곱하기 위해 곱할 수있는 가장 높은 숫자는 6.7 * 7 = 49입니다.

숫자의 제곱근을 찾는 것이 효율성을위한 것입니다. 예. 36의 요인을 찾으려한다면 36을 곱하기 위해 곱할 수있는 가장 높은 숫자는 6.7 * 7 = 49입니다.

그러므로 36의 모든 요인에 6을 곱하거나 더 작은 수를 곱해야합니다.

==============================

6.

def is_prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True  
    for n in range(2, x):
        if x % n ==0:
            return False
    return True

==============================
7.당신이 작성하는 모든 코드는 효율적이어야합니다. 가장 쉬운 방법은 숫자 'n'을 2에서 (n-1)로 나눌 수 있는지 확인하는 것입니다. 이것은 매우 큰 숫자를 고려할 때 많은 시간이 걸립니다. 제곱근 방법은 적은 수의 비교로 코드를 더 빠르게 만들 수 있습니다. 알고리즘 설계 및 분석의 복잡성에 대해 읽어보십시오.

당신이 작성하는 모든 코드는 효율적이어야합니다. 가장 쉬운 방법은 숫자 'n'을 2에서 (n-1)로 나눌 수 있는지 확인하는 것입니다. 이것은 매우 큰 숫자를 고려할 때 많은 시간이 걸립니다. 제곱근 방법은 적은 수의 비교로 코드를 더 빠르게 만들 수 있습니다. 알고리즘 설계 및 분석의 복잡성에 대해 읽어보십시오.
==============================
8.나는 늦었는지 모르지만 장래에 누군가를 돕기 위해 여기에 남겨 둘 것입니다.

나는 늦었는지 모르지만 장래에 누군가를 돕기 위해 여기에 남겨 둘 것입니다.

프로그램에서 계산할 숫자 범위를 줄이기 위해 (n)의 제곱근 즉 int (n ** 0.5)를 사용합니다.

예를 들어, 우리는 100의 소수를 테스트하기 위해 시범 분할을 할 수 있습니다. 100의 모든 약수를 봅시다.

2, 4, 5, 10, 20, 25, 50 여기서 우리는 가장 큰 요소가 100/2 = 50이라는 것을 알 수 있습니다. 이것은 모든 n에 해당됩니다 : 모든 제수는 n / 2보다 작거나 같습니다. 약수를 면밀히 살펴보면 일부는 중복되는 것을 볼 수 있습니다. 목록을 다르게 작성하면

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 중복성이 명백해진다. 우리가 √100 인 10에 이르면 약수가 그냥 뒤집어 반복됩니다. 따라서, 우리는 √n보다 큰 시험 약수를 더 제거 할 수 있습니다.

16과 같은 다른 번호를 가져 가십시오.

그것의 약수는 2,4,8

16 = 2 * 8, 4 * 4, 8 * 2.

16의 제곱근 인 4에 도달 한 후에 우리는 이미 2 * 8로했던 8 * 2를 반복했다는 것을 알 수 있습니다. 이 패턴은 모든 숫자에 해당됩니다.

반복을 피하기 위해 숫자 n의 제곱근까지의 소수성을 테스트합니다.

그래서 우리는 부동 소수점으로 범위를 원하지 않기 때문에 제곱근을 int로 변환합니다.

자세한 정보는 위키피디아의 소수 테스트를 읽으십시오.
==============================
9.이 메서드는 여기에있는 재귀 및 열거 형 메서드보다 느리지 만 Wilson의 정리를 사용하며 한 줄에 불과합니다.

이 메서드는 여기에있는 재귀 및 열거 형 메서드보다 느리지 만 Wilson의 정리를 사용하며 한 줄에 불과합니다.
```
from math import factorial

def is_prime(x):
    return factorial(x - 1)  % x == x - 1
```
==============================
10.
```
isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])
```
그리고 그것을 사용하는 방법을 간다.
```
isPrime(2) == False
isPrime(5) == True
isPrime(7) == True
```
사용할 수있는 모든 소수를 찾으려면 :
```
filter(isPrime, range(4000)[2:])[:5]
=> [2, 3, 5, 7, 11]
```
이 경우 5는 발견 될 소수의 수와 소수가 검색 될 4000 개의 최대 범위를 나타냅니다.

==============================

11.

def is_prime(x):  
    if x < 2:  
        return False  
    for n in range(2, (x) - 1):  
        if x % n == 0:  
            return False  
    return True

==============================

12.이것은 나의 방법이다.

이것은 나의 방법이다.

import math

def isPrime(n):
    'Returns True if n is prime, False if n is not prime. Will not work if n is 0 or 1'

    # Make sure n is a positive integer
    n = abs(int(n))

    # Case 1: the number is 2 (prime)
    if n == 2: return True

    # Case 2: the number is even (not prime)
    if n % 2 == 0: return False

    # Case 3: the number is odd (could be prime or not)

    # Check odd numbers less than the square root for possible factors 
    r = math.sqrt(n)
    x = 3 
    while x <= r:
        if n % x == 0: return False  # A factor was found, so number is not prime
        x += 2 # Increment to the next odd number

    # No factors found, so number is prime  
    return True

원래 질문에 답하기 위해, n ** 0.5는 n의 근의 제곱과 같습니다. 복합 숫자는 항상 제곱근보다 작거나 같은 인수를 갖기 때문에이 숫자 뒤에 오는 요소를 확인하지 않아도됩니다. 이것은 모든 n에 대해 2와 n 사이의 모든 요소를 확인하는 것보다 빠릅니다. 더 적은 수를 확인하기 때문에 n이 커짐에 따라 더 많은 시간을 절약 할 수 있습니다.

==============================

13.

def isPrime(num,div=2):
    if(num==div):
        return True
    elif(num % div == 0):
        return False
    else:
        return isPrime(num,div+1)

==============================
14.int (n ** 0.5)는 sqrt (n)의 floor 값으로, n (n ** 2)의 2의 힘과 혼동을 일으 킵니다. n이 소수가 아닌 경우, i * j = n과 같이 두 개의 숫자 1
int (n ** 0.5)는 sqrt (n)의 floor 값으로, n (n ** 2)의 2의 힘과 혼동을 일으 킵니다. n이 소수가 아닌 경우, i * j = n과 같이 두 개의 숫자 1
이제, i, j 중 하나가 sqrt (n)보다 크거나 같다고 가정하면 sqrt (n) * sqrt (n) = n 이후 - 다른 하나는 sqrt보다 작거나 같아야 함을 의미합니다. (엔).

이 경우 [2, sqrt (n)] 범위의 정수를 반복하는 것이 좋습니다. 그리고 그것은 정확히 게시 된 코드가하는 일입니다.

실제 스마트 캐쉬로 나오려면 다음 한 줄짜리 기능을 사용하십시오.

import re def is_prime(n): return not re.match(r'^1?$|^(11+?)\1+$',n*'1')

"magic regex"에 대한 설명은 여기에서 찾을 수 있습니다.

==============================
15.

def fun(N):#prime test if N>1 : for _ in xrange(5): Num=randint(1,N-1) if pow(Num,N-1,N)!=1: return False return True return False

숫자가 소수 일 경우 거짓, 그렇지 않으면 거짓

==============================
16.이것은 내 np 방법입니다.

이것은 내 np 방법입니다.

def is_prime(x): if x < 4: return True if all([(x > 2), (x % 2 == 0)]): return False else: return np.array([*map(lambda y: ((x % y) == 0).sum(), np.arange(1, x + 1))]).sum() == 2

성능은 다음과 같습니다.

%timeit is_prime(2) %timeit is_prime(int(1e3)) %timeit is_prime(5003) 10000 loops, best of 3: 31.1 µs per loop 10000 loops, best of 3: 33 µs per loop 10 loops, best of 3: 74.2 ms per loop

==============================
17.

def is_prime(n): n=abs(n) if n<2: #Numbers less than 2 are not prime numbers return "False" elif n==2: #2 is a prime number return "True" else: for i in range(2,n): # Highlights range numbers that can't be a factor of prime number n. if n%i==0: return "False" #if any of these numbers are factors of n, n is not a prime number return "True" # This is to affirm that n is indeed a prime number after passing all three tests

==============================
18.의사 코드 (https://en.wikipedia.org/wiki/Primality_test)를 Python으로 구현했습니다.이 도움이 되었으면합니다.

의사 코드 (https://en.wikipedia.org/wiki/Primality_test)를 Python으로 구현했습니다.이 도움이 되었으면합니다.

# original pseudocode https://en.wikipedia.org/wiki/Primality_test def isPrime(n): # Corner Cases if (n<= 1): return False elif (n<= 3): return True elif (n%2 == 0 or n%3 == 0): return False i = 5 while i*i<=n: if (n%i==0 or n%(i+2)==0): return False i += 6 return True; %timeit isPrime(800)

==============================
19.아주 간단합니다!

아주 간단합니다!

def prime(x): if x == 1: return False else: for a in range(2,x): if x % a == 0: return False return True

==============================
20.번호 1은 소수이거나 복합으로 간주되지 않는 특별한 경우입니다. 자세한 정보는 http://mathworld.wolfram.com/PrimeNumber.html을 참조하십시오.

번호 1은 소수이거나 복합으로 간주되지 않는 특별한 경우입니다. 자세한 정보는 http://mathworld.wolfram.com/PrimeNumber.html을 참조하십시오.

과, (n ** 0.5) -> 그러면 'n'의 '제곱근'이 생깁니다. 그것이 "0.5 또는 1/2의 힘으로 키워지기 때문에"

그리고 우리는 왜 그 일을합니까? 숫자 400을 예로 들어 보겠습니다. a * b 형식으로 표현할 수 있습니다.

1*400 = 400 2*200 = 400 4*100 = 400 5*80 = 400 8*50 = 400 10*40 = 400 16*25 = 400 20*20 = 400 25*16 = 400 40*10 = 400 50*8 = 400 80*5 = 400 100*4 = 400 200*2 = 400 400*1 = 400

400의 제곱근은 20입니다. 'a'가 20 'b'에 도달 할 때 감소하기 시작하기 때문에 20까지 나누기 만 확인하면된다는 것을 알 수 있습니다. 그래서 궁극적으로 우리는 제곱근보다 작은 숫자로 나눗셈을 검사하고 있습니다.

==============================
21.나는 내가 말한 어떤 것보다 빠르다고 생각되는 새로운 해결책을 가지고있다. 파이썬에서의 함수

나는 내가 말한 어떤 것보다 빠르다고 생각되는 새로운 해결책을 가지고있다. 파이썬에서의 함수

이는 다음과 같은 아이디어에 기반합니다. N / D = R 임의의 수 N에 대해 N을 나눌 수있는 가능한 최소 수 (소수가 아닌 경우)는 D = 2이고 해당 결과 R은 (N / 2) (가장 높음)입니다.

D가 커질수록 결과 R은 작아진다. 예 : D = 3으로 나눈 결과 R = (N / 3) 그래서 N이 N에 의해 나눌 수 있는지를 검사 할 때 우리는 그것이 R로 나눌 수 있는지를 검사하고 있습니다.

그래서 D가 커지고 R이 작아 질 때까지 (D == R == 제곱근 (N))

그 다음에 우리는 단지 2에서 sqrt (N) 시간을 절약 할 수있는 또 다른 팁은 홀수를 확인하는 것입니다. 번호가 짝수로 나눌 수 있기 때문에 2로 나눌 수도 있습니다.

시퀀스는 3,5,7,9, ......, sqrt (N)이 될 것입니다.

import math def IsPrime (n): if (n <= 1 or n % 2 == 0):return False if n == 2:return True for i in range(3,int(math.sqrt(n))+1,2): if (n % i) == 0: return False return True

==============================
22.

for i in range(2,5003): j = 2 c = 0 while j < i: if i % j == 0: c = 1 j = j + 1 else: j = j + 1 if c == 0: print(str(i) + ' is a prime number') else: c = 0

==============================
23.여기 내거야.

여기 내거야.

import math def is_prime(num): if num % 2 == 0 and num > 2: return False for i in range(3, int(math.sqrt(num)) + 1, 2): if num % i == 0: return False return True

==============================
24.

def is_prime(x): if x<2: return False elif x == 2: return True else: for n in range(2, x): if x%n==0: return False return True

==============================
25.Srsly 얘들 아 ... 왜 이런 식의 간단한 방법에 대해 많은 코드 라인이 필요합니까? 내 솔루션은 다음과 같습니다.

Srsly 얘들 아 ... 왜 이런 식의 간단한 방법에 대해 많은 코드 라인이 필요합니까? 내 솔루션은 다음과 같습니다.

def isPrime(a): div = a - 1 res = True while(div > 1): if a % div == 0: res = False div = div - 1 return res

from https://stackoverflow.com/questions/15285534/isprime-function-for-python-language by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] 파이썬이 UCS-2 또는 UCS-4로 컴파일되었는지 확인하는 방법은 무엇입니까?  (0) 2018.10.07

[PYTHON] Python에서 "ImportError : No module named ..."오류를 수정하는 방법은 무엇입니까?  (0) 2018.10.07

[PYTHON] 파이썬에서 프록시를 사용하여 Selenium Webdriver 실행하기  (0) 2018.10.07

[PYTHON] 파이썬 요청 파일 업로드  (0) 2018.10.07

[PYTHON] 여러 프로세스간에 결과 큐 공유  (0) 2018.10.07

복붙노트

[PYTHON] 파이썬 언어를위한 isPrime 함수

파이썬 언어를위한 isPrime 함수

해결법

1.인터넷 주변에 떠있는 많은 소수 테스트 중 다음과 같은 주요 테스트를 고려하십시오.

2.n ** .5에서는 n을 제곱하지 않고 제곱근을 취합니다.

3.질문은 조금 전에 묻지 만, 나는 당신을위한 더 짧은 해결책을 가지고있다.

4.부동 소수점 연산은 아래에서 수행되지 않습니다. 이것은 더 빠르며 더 높은 논증을 용인 할 것입니다. 당신이 제곱근에만 가야만하는 이유는 숫자의 제곱근보다 큰 인수가 있다면 그 인수도 제곱근보다 작기 때문입니다.

5.숫자의 제곱근을 찾는 것이 효율성을위한 것입니다. 예. 36의 요인을 찾으려한다면 36을 곱하기 위해 곱할 수있는 가장 높은 숫자는 6.7 * 7 = 49입니다.

6.

8.나는 늦었는지 모르지만 장래에 누군가를 돕기 위해 여기에 남겨 둘 것입니다.

9.이 메서드는 여기에있는 재귀 및 열거 형 메서드보다 느리지 만 Wilson의 정리를 사용하며 한 줄에 불과합니다.

10.

11.

12.이것은 나의 방법이다.

13.

15.

16.이것은 내 np 방법입니다.

17.

18.의사 코드 (https://en.wikipedia.org/wiki/Primality_test)를 Python으로 구현했습니다.이 도움이 되었으면합니다.

19.아주 간단합니다!

20.번호 1은 소수이거나 복합으로 간주되지 않는 특별한 경우입니다. 자세한 정보는 http://mathworld.wolfram.com/PrimeNumber.html을 참조하십시오.

21.나는 내가 말한 어떤 것보다 빠르다고 생각되는 새로운 해결책을 가지고있다. 파이썬에서의 함수

22.

23.여기 내거야.

24.

25.Srsly 얘들 아 ... 왜 이런 식의 간단한 방법에 대해 많은 코드 라인이 필요합니까? 내 솔루션은 다음과 같습니다.

'PYTHON' 카테고리의 다른 글

티스토리툴바

[PYTHON] 파이썬이 UCS-2 또는 UCS-4로 컴파일되었는지 확인하는 방법은 무엇입니까? (0)	2018.10.07
[PYTHON] Python에서 "ImportError : No module named ..."오류를 수정하는 방법은 무엇입니까? (0)	2018.10.07
[PYTHON] 파이썬에서 프록시를 사용하여 Selenium Webdriver 실행하기 (0)	2018.10.07
[PYTHON] 파이썬 요청 파일 업로드 (0)	2018.10.07
[PYTHON] 여러 프로세스간에 결과 큐 공유 (0)	2018.10.07