가장 컴팩트 한 매핑을 만드는 방법 n → isprime (n) 최대 한계 N?
당연히 bool isprime(number)쿼리 할 수있는 데이터 구조가 있기 때문입니다.
I는 최상의 알고리즘을 정의 N은 일정 범위 (1, N], 가장 낮은 메모리 소비 데이터 구조를 생성하는 알고리즘으로,.
내가 찾던 중 단지 예제 : I는 각 홀수 나타낼 수 예를 들어 주어진 숫자 범위 (1, 10)에 대해 1 비트로 3에서 시작합니다.1110
다음 사전을 더 많이 압착 할 수 있습니다. 몇 가지 작업으로 5의 배수를 제거 할 수는 있지만 1, 3, 7 또는 9로 끝나는 숫자는 비트 배열에 있어야합니다.
문제를 어떻게 해결합니까?
원시성 테스트 를 수행하는 방법에는 여러 가지가 있습니다 .
실제로 쿼리 할 데이터 구조는 없습니다. 테스트 할 숫자가 많으면 확률 테스트 가 더 빠르기 때문에 확률 테스트를 실행 한 다음 결정적 테스트 를 수행하여 숫자가 소수인지 확인해야합니다.
가장 빠른 알고리즘에 대한 계산은 희미한 마음을위한 것이 아니라는 것을 알아야합니다.
일반적인 프라임 테스트를위한 가장 빠른 알고리즘은 AKS 입니다. Wikipedia 기사는 길이에 대해 설명하고 원본 용지에 연결합니다.
큰 숫자를 찾으려면 Mersenne 소수 와 같은 특수한 형태의 소수를 찾으십시오 .
내가 일반적으로 구현하는 알고리즘 (쉽게 이해하고 코딩하기)은 다음과 같습니다 (파이썬에서).
def isprime(n):
"""Returns True if n is prime."""
if n == 2:
return True
if n == 3:
return True
if n % 2 == 0:
return False
if n % 3 == 0:
return False
i = 5
w = 2
while i * i <= n:
if n % i == 0:
return False
i += w
w = 6 - w
return True
클래식 O(sqrt(N))알고리즘 의 변형입니다 . 그것은 (2, 3 제외) 주요 양식의 사실 사용 6k - 1또는 6k + 1만이 양식의 약수에 보이는합니다.
때로는 속도를 정말로 원 하고 범위가 제한되는 경우 Fermat의 작은 정리를 기반으로 의사 프라임 테스트를 구현합니다 . 실제로 더 빠른 속도를 원한다면 (즉, O (sqrt (N)) 알고리즘을 모두 피하십시오), 오 탐지를 미리 계산하고 ( 카 마이클 숫자 참조 ) 이진 검색을 수행합니다. 이것은 지금까지 구현 한 것 중 가장 빠른 테스트이며, 유일한 단점은 범위가 제한되어 있다는 것입니다.
제 생각에는 가장 좋은 방법은 이전에 사용했던 것을 사용하는 것입니다.
N인터넷에 첫 번째 소수는 5 천만N 이상으로 늘어났다 . 파일을 다운로드하여 사용하면 다른 방법보다 훨씬 빠릅니다.
당신이 당신의 자신의 소수를 만들기위한 실제 알고리즘을 원하는 경우에, 위키 백과는 소수에 좋은 물건의 모든 종류가 여기에 그 일을위한 다양한 방법에 대한 링크, 프라임 테스트를 포함, 여기 , 두 확률 기반 및 빠른 결정 방법.
사람들이이 같은 일을 계속 반복해서 멈출 수 있도록 처음 10 억 개 (또는 그 이상)의 프라임을 찾아서 어딘가에 인터넷에 게시하려는 공동 노력이 있어야합니다. ... :-)
bool isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
this is just c++ implementation of above AKS algorithm
https://ko.wikipedia.org/wiki/AKS_primality_test
Wikipedia에 따르면 에라토스테네스의 체 는 복잡 O(n * (log n) * (log log n))하고 O(n)메모리 가 필요 하므로 특히 많은 수를 테스트하지 않는 경우 시작하기에 좋은 곳입니다.
파이썬 3에서 :
def is_prime(a):
if a < 2:
return False
elif a!=2 and a % 2 == 0:
return False
else:
return all (a % i for i in range(3, int(a**0.5)+1))
설명 : 소수는 1과 2로만 나눌 수있는 숫자입니다. 예 : 2,3,5,7 ...
1) a <2 인 경우 : "a"가 2보다 작은 경우 소수가 아닙니다.
2) elif a! = 2 and a % 2 == 0 : "a"를 2로 나눌 수 있으면 확실히 소수가 아닙니다. 그러나 a = 2이면 소수이므로 평가하고 싶지 않습니다. 따라서 조건 a! = 2
3) 모두 반환 (범위 (3, int (a 0.5) +1) 에서 i에 대한 % i ) : ** 먼저 파이썬에서 all () 명령의 기능을 살펴보십시오. 3에서 시작하여 "a"를 제곱근 (a ** 0.5)으로 나눕니다. "a"를 나눌 수 있으면 출력은 False입니다. 왜 제곱근입니까? a = 16이라고합시다. 제곱근은 16 = 4입니다. 우리는 15까지 평가할 필요가 없습니다. 우리는 소수가 아니라고 말하기 위해 4까지만 확인하면됩니다.
추가 : 범위 내의 모든 소수를 찾기위한 루프.
for i in range(1,100):
if is_prime(i):
print("{} is a prime number".format(i))
가장 인기있는 제안의 효율성을 비교하여 숫자가 소수인지 확인했습니다. 나는에 사용 python 3.6했다 ubuntu 17.10; 최대 100.000의 숫자로 테스트했습니다 (아래 코드를 사용하여 더 큰 숫자로 테스트 할 수 있음).
이 첫 번째 줄거리는 함수 (내 대답에서 아래에 자세히 설명되어 있음)를 비교하여 마지막 함수가 숫자를 늘릴 때 첫 번째 함수만큼 빠르게 성장하지 않음을 보여줍니다.
그리고 두 번째 그림에서 소수의 경우 시간이 꾸준히 증가하지만 소수가 아닌 숫자는 시간이 너무 빨리 증가하지 않음을 알 수 있습니다 (대부분이 초기에 제거 될 수 있기 때문).
내가 사용한 기능은 다음과 같습니다.
이 대답 과 이 답변이 사용 구조를 제안했다
all():def is_prime_1(n): return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1))이 답변 은 일종의 while 루프를 사용했습니다.
def is_prime_2(n): if n <= 1: return False if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True이 답변 에는
for루프 버전 이 포함되어 있습니다 .def is_prime_3(n): if n <= 1: return False if n % 2 == 0 and n > 2: return False for i in range(3, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True그리고 다른 답변의 몇 가지 아이디어를 새로운 아이디어로 혼합했습니다.
def is_prime_4(n): if n <= 1: # negative numbers, 0 or 1 return False if n <= 3: # 2 and 3 return True if n % 2 == 0 or n % 3 == 0: return False for i in range(5, int(math.sqrt(n)) + 1, 2): if n % i == 0: return False return True
변형을 비교하는 스크립트는 다음과 같습니다.
import math
import pandas as pd
import seaborn as sns
import time
from matplotlib import pyplot as plt
def is_prime_1(n):
...
def is_prime_2(n):
...
def is_prime_3(n):
...
def is_prime_4(n):
...
default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4)
def assert_equal_results(func_list=default_func_list, n):
for i in range(-2, n):
r_list = [f(i) for f in func_list]
if not all(r == r_list[0] for r in r_list):
print(i, r_list)
raise ValueError
print('all functions return the same results for integers up to {}'.format(n))
def compare_functions(func_list=default_func_list, n):
result_list = []
n_measurements = 3
for f in func_list:
for i in range(1, n + 1):
ret_list = []
t_sum = 0
for _ in range(n_measurements):
t_start = time.perf_counter()
is_prime = f(i)
t_end = time.perf_counter()
ret_list.append(is_prime)
t_sum += (t_end - t_start)
is_prime = ret_list[0]
assert all(ret == is_prime for ret in ret_list)
result_list.append((f.__name__, i, is_prime, t_sum / n_measurements))
df = pd.DataFrame(
data=result_list,
columns=['f', 'number', 'is_prime', 't_seconds'])
df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2))
print('df.shape:', df.shape)
print()
print('', '-' * 41)
print('| {:11s} | {:11s} | {:11s} |'.format(
'is_prime', 'count', 'percent'))
df_sub1 = df[df['f'] == 'is_prime_1']
print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
'all', df_sub1.shape[0], 100))
for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems():
print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
str(is_prime), count, count * 100 / df_sub1.shape[0]))
print('', '-' * 41)
print()
print('', '-' * 69)
print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format(
'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)'))
for f, df_sub1 in df.groupby(['f', ]):
col = df_sub1['t_micro_seconds']
print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13))
print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
f, 'all', col.min(), col.mean(), col.max()))
for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]):
col = df_sub2['t_micro_seconds']
print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
f, str(is_prime), col.min(), col.mean(), col.max()))
print('', '-' * 69)
return df
함수를 실행하면 compare_functions(n=10**5)(최대 100.000까지)이 출력을 얻습니다.
df.shape: (400000, 5)
-----------------------------------------
| is_prime | count | percent |
| all | 100,000 | 100.0 % |
| False | 90,408 | 90.4 % |
| True | 9,592 | 9.6 % |
-----------------------------------------
---------------------------------------------------------------------
| f | is_prime | t min (us) | t mean (us) | t max (us) |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1 | all | 0.57 | 2.50 | 154.35 |
| is_prime_1 | False | 0.57 | 1.52 | 154.35 |
| is_prime_1 | True | 0.89 | 11.66 | 55.54 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2 | all | 0.24 | 1.14 | 304.82 |
| is_prime_2 | False | 0.24 | 0.56 | 304.82 |
| is_prime_2 | True | 0.25 | 6.67 | 48.49 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3 | all | 0.20 | 0.95 | 50.99 |
| is_prime_3 | False | 0.20 | 0.60 | 40.62 |
| is_prime_3 | True | 0.58 | 4.22 | 50.99 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4 | all | 0.20 | 0.89 | 20.09 |
| is_prime_4 | False | 0.21 | 0.53 | 14.63 |
| is_prime_4 | True | 0.20 | 4.27 | 20.09 |
---------------------------------------------------------------------
그런 다음 함수를 실행하면 compare_functions(n=10**6)(최대 1.000.000까지)이 출력을 얻습니다.
df.shape: (4000000, 5)
-----------------------------------------
| is_prime | count | percent |
| all | 1,000,000 | 100.0 % |
| False | 921,502 | 92.2 % |
| True | 78,498 | 7.8 % |
-----------------------------------------
---------------------------------------------------------------------
| f | is_prime | t min (us) | t mean (us) | t max (us) |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1 | all | 0.51 | 5.39 | 1414.87 |
| is_prime_1 | False | 0.51 | 2.19 | 413.42 |
| is_prime_1 | True | 0.87 | 42.98 | 1414.87 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2 | all | 0.24 | 2.65 | 612.69 |
| is_prime_2 | False | 0.24 | 0.89 | 322.81 |
| is_prime_2 | True | 0.24 | 23.27 | 612.69 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3 | all | 0.20 | 1.93 | 67.40 |
| is_prime_3 | False | 0.20 | 0.82 | 61.39 |
| is_prime_3 | True | 0.59 | 14.97 | 67.40 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4 | all | 0.18 | 1.88 | 332.13 |
| is_prime_4 | False | 0.20 | 0.74 | 311.94 |
| is_prime_4 | True | 0.18 | 15.23 | 332.13 |
---------------------------------------------------------------------
다음 스크립트를 사용하여 결과를 플로팅했습니다.
def plot_1(func_list=default_func_list, n):
df_orig = compare_functions(func_list=func_list, n=n)
df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20]
sns.lmplot(
data=df_filtered, x='number', y='t_micro_seconds',
col='f',
# row='is_prime',
markers='.',
ci=None)
plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3))
plt.show()
sympy를 사용할 수 있습니다 .
import sympy
sympy.ntheory.primetest.isprime(33393939393929292929292911111111)
True
교묘 한 문서에서. 첫 번째 단계는 사소한 요소를 찾는 것인데, 발견되면 빠른 복귀가 가능합니다. 다음으로 체가 충분히 크면 체에서 이분법 검색을 사용하십시오. 소수의 경우, 일련의 결정론적인 Miller-Rabin 테스트는 해당 범위에 반례가없는 것으로 알려진 염기로 수행됩니다. 마지막으로이 수가 2 ^ 64보다 크면 강력한 BPSW 테스트가 수행됩니다. 이것은 가능한 주요 테스트이며 반례가 존재한다고 생각되지만 알려진 반례는 없습니다.
숫자가 큰 경우 후보 번호 N을 sqrt (N)보다 작은 숫자로 나눌 수 있는지 순진하게 확인할 수 없습니다. Miller-Rabin 원시성 테스트 와 같이 훨씬 더 확장 가능한 테스트가 있습니다 . 아래는 파이썬으로 구현 한 것입니다.
def is_prime(x):
"""Fast implementation fo Miller-Rabin primality test, guaranteed to be correct."""
import math
def get_sd(x):
"""Returns (s: int, d: int) for which x = d*2^s """
if not x: return 0, 0
s = 0
while 1:
if x % 2 == 0:
x /= 2
s += 1
else:
return s, x
if x <= 2:
return x == 2
# x - 1 = d*2^s
s, d = get_sd(x - 1)
if not s:
return False # divisible by 2!
log2x = int(math.log(x) / math.log(2)) + 1
# As long as Riemann hypothesis holds true, it is impossible
# that all the numbers below this threshold are strong liars.
# Hence the number is guaranteed to be a prime if no contradiction is found.
threshold = min(x, 2*log2x*log2x+1)
for a in range(2, threshold):
# From Fermat's little theorem if x is a prime then a^(x-1) % x == 1
# Hence the below must hold true if x is indeed a prime:
if pow(a, d, x) != 1:
for r in range(0, s):
if -pow(a, d*2**r, x) % x == 1:
break
else:
# Contradicts Fermat's little theorem, hence not a prime.
return False
# No contradiction found, hence x must be a prime.
return True
이를 사용하여 큰 소수를 찾을 수 있습니다.
x = 10000000000000000000000000000000000000000000000000000000000000000000000000000
for e in range(1000):
if is_prime(x + e):
print('%d is a prime!' % (x + e))
break
# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!
임의의 정수를 테스트하는 경우 Miller-Rabin에 전화하기 전에 후보 번호를 1000보다 작은 소수로 나눌 수 있는지 먼저 테스트하고 싶을 것입니다. 이는 10444344345와 같이 명백한 비 프라임을 필터링하는 데 도움이됩니다.
파이썬 3 :
def is_prime(a):
return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))
파티에 너무 늦었지만 이것이 도움이되기를 바랍니다. 큰 소수를 찾고 있다면 이것은 관련이 있습니다.
큰 홀수를 테스트하려면 Fermat 테스트 및 / 또는 Miller-Rabin 테스트를 사용해야합니다.
이 테스트는 모듈 식 지수를 사용하는데, 이는 매우 비쌉니다. n비트 지수화를 위해서는 최소한 n큰 정수 곱셈과 n큰 정수 분할이 필요합니다. 이는 모듈 식 지수의 복잡성이 O (n³)임을 의미합니다.
따라서 큰 총을 사용하기 전에, 약간의 시험 분할을 수행해야합니다. 그러나 순진하게하지 마십시오. 빠르게 할 수있는 방법이 있습니다. 먼저 큰 정수에 사용하는 단어에 맞는 수만큼 소수를 곱하십시오. 32 비트 단어를 사용하는 경우 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615를 곱하고 유클리드 알고리즘을 사용하여 테스트 한 숫자로 최대 공약수를 계산하십시오. 첫 번째 단계 후에 숫자는 단어 크기 아래로 줄어들고 완전한 큰 정수 나누기를 수행하지 않고 알고리즘을 계속합니다. GCD! = 1 인 경우, 곱한 소수 중 하나가 숫자를 나누므로 소수가 아니라는 증거가됩니다. 그런 다음 31 * 37 * 41 * 43 * 47 = 95041567 등으로 계속 진행하십시오.
이 방법으로 수백 (또는 수천)의 소수를 테스트 한 후에는 40 라운드의 Miller-Rabin 테스트를 수행하여 숫자가 소수임을 확인하고, 40 라운드 후에는 숫자가 소수임을 확신 할 수 있습니다. 아닙니다 (하드웨어 오작동 가능성이 높습니다 ...).
나는 (2 ^ 61) -1까지 작동하는 주요 기능을 가지고 있습니다.
from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))
설명:
이 all()기능은 다음과 같이 재정의 할 수 있습니다.
def all(variables):
for element in variables:
if not element: return False
return True
이 all()함수는 일련의 부울 / 숫자를 거쳐 False0 또는 을 보이면 반환 합니다 False.
이 sqrt()함수는 숫자의 제곱근 을 수행하는 것 입니다.
예를 들면 다음과 같습니다.
>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10
이 num % x부분은 나머지 num / x를 반환합니다 .
마지막으로 2에서 시작하여 다음에 끝나는 목록 을 range(2, int(sqrt(num)))만듭니다.int(sqrt(num)+1)
범위에 대한 자세한 내용은이 웹 사이트를 참조하십시오 !
num > 1변수가있는 경우 부분은 확인되는 num1과 0이 소수로 간주되지 않습니다 becuase,보다 큰 1입니다.
나는 이것이 도움이되기를 바랍니다 :)
파이썬에서 :
def is_prime(n):
return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))
수학 형식에서 파이썬으로 직접 변환하려면 all (n % p! = 0 ...) 을 사용하지만 p의 모든 값을 엄격하게 평가해야합니다. 되지 않은 참 값이 발견되면 버전은 일찍 종료 할 수 있습니다.
소수의 자바 스크립트를위한 최고의 알고리즘
function isPrime(num) {
if (num <= 1) return false;
else if (num <= 3) return true;
else if (num % 2 == 0 || num % 3 == 0) return false;
var i = 5;
while (i * i <= num) {
if (num % i == 0 || num % (i + 2) == 0) return false;
i += 6;
}
return true
}
import math
import time
def check_prime(n):
if n == 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
from_i = 3
to_i = math.sqrt(n) + 1
for i in range(from_i, int(to_i), 2):
if n % i == 0:
return False
return True
언급 된 AKS 알고리즘과 유사한 아이디어
public static boolean isPrime(int n) {
if(n == 2 || n == 3) return true;
if((n & 1 ) == 0 || n % 3 == 0) return false;
int limit = (int)Math.sqrt(n) + 1;
for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
if(n % i == 0) return false;
numChecks++;
}
return true;
}
범위 내의 숫자가 소수인지 확인합니다.
#!usr/bin/python3
def prime_check(*args):
for arg in args:
if arg > 1: # prime numbers are greater than 1
for i in range(2,arg): # check for factors
if(arg % i) == 0:
print(arg,"is not Prime")
print(i,"times",arg//i,"is",arg)
break
else:
print(arg,"is Prime")
# if input number is less than
# or equal to 1, it is not prime
else:
print(arg,"is not Prime")
return
# Calling Now
prime_check(*list(range(101))) # This will check all the numbers in range 0 to 100
prime_check(#anynumber) # Put any number while calling it will check.
myInp=int(input("Enter a number: "))
if myInp==1:
print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
for i in range(2,myInp//2+1):
if myInp%i==0:
print("The Number {} is not a prime no".format(myInp))
print("Because",i,"times",myInp//i,"is",myInp)
break
else:
print("The Number {} is a prime no".format(myInp))
else:
print("Alas the no {} is a not a prime no".format(myInp))
이런 식으로 시도해 볼 수 있습니다.
def main():
try:
user_in = int(input("Enter a number to determine whether the number is prime or not: "))
except ValueError:
print()
print("You must enter a number!")
print()
return
list_range = list(range(2,user_in+1))
divisor_list = []
for number in list_range:
if user_in%number==0:
divisor_list.append(number)
if len(divisor_list) < 2:
print(user_in, "is a prime number!")
return
else:
print(user_in, "is not a prime number!")
return
main()
이전 답변의 대부분은 정확하지만 여기에 숫자가 소수인지 테스트하는 또 다른 방법이 있습니다. 새로 고침으로 소수 는 1보다 큰 정수이며 1과 그 자체 만 요소입니다. ( source )
해결책:
일반적으로 루프를 만들고 숫자 테스트를 시작하여 1,2,3으로 나눌 수 있는지 확인합니다 ... 테스트중인 숫자까지 ...하지만 확인 시간을 줄이기 위해 숫자를 다음과 같이 나눌 수 있습니다 숫자를 반으로 나눌 수 없으므로 숫자 값의 반입니다. 예를 들어 100이 소수 인 경우 최대 50까지 반복 할 수 있습니다.
실제 코드 :
def find_prime(number):
if(number ==1):
return False
# we are dividiing and rounding and then adding the remainder to increment !
# to cover not fully divisible value to go up forexample 23 becomes 11
stop=number//2+number%2
#loop through up to the half of the values
for item in range(2,stop):
if number%item==0:
return False
print(number)
return True
if(find_prime(3)):
print("it's a prime number !!")
else:
print("it's not a prime")
Java 스트림을 사용하여 O (sqrt (n))에서이를 구현할 수 있습니다. noneMatch는 결과를 결정할 필요가없는 경우 작업을 중지하는 shortCircuiting 메소드입니다.
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");
Java-8 스트림과 람다의 도움으로 단 몇 줄로 다음과 같이 구현할 수 있습니다.
public static boolean isPrime(int candidate){
int candidateRoot = (int) Math.sqrt( (double) candidate);
return IntStream.range(2,candidateRoot)
.boxed().noneMatch(x -> candidate % x == 0);
}
성능은 O (sqrt (N)) 과 비슷해야합니다 . 누군가가 유용하다고 생각할 수도 있습니다.
대답은 다음과 같습니다.
def isprime(num):
return num <= 3 or (num + 1) % 6 == 0 or (num - 1) % 6 == 0
아래 속성 중 하나라도 True이면이 함수는 True를 반환합니다. 이러한 속성은 프라임이 무엇인지 수학적으로 정의합니다.
- 숫자가 3보다 작거나 같습니다
- 숫자 + 1은 6으로 나눌 수 있습니다
- 숫자-1은 6으로 나눌 수 있습니다
소수는 1과 그 자체로만 나눌 수있는 숫자입니다. 다른 모든 숫자는 composite 라고 합니다.
소수를 찾는 가장 간단한 방법은 입력 숫자가 복합 숫자인지 확인하는 것입니다.
function isPrime(number) {
// Check if a number is composite
for (let i = 2; i < number; i++) {
if (number % i === 0) {
return false;
}
}
// Return true for prime numbers
return true;
}
프로그램은 number모든 정수로 값을 1에서 그 값 으로 나눠야합니다 . 이 숫자를 1 개만으로 균등하게 나눌 수 없으면 복합 숫자입니다.
i소수와 복합 수는 1로 균등하게 나눌 수 있으므로 변수의 초기 값은 2 여야합니다.
for (let i = 2; i < number; i++)
그렇다면 같은 이유 i보다 적습니다 number. 소수와 복합 수는 모두 균등하게 나눌 수 있습니다. 따라서 확인할 이유가 없습니다.
그런 다음 나머지 연산자를 사용하여 변수를 균등하게 나눌 수 있는지 확인합니다.
if (number % i === 0) {
return false;
}
나머지가 0이면 number균등하게 나눌 수 있음을 의미 하므로 복합 수이며 false를 반환합니다.
입력 한 숫자가 조건을 충족하지 않으면 소수이고 함수는 true를 리턴한다는 의미입니다.
가장 작은 메모리? 이것은 가장 작지는 않지만 올바른 방향으로 나아가는 단계입니다.
class PrimeDictionary {
BitArray bits;
public PrimeDictionary(int n) {
bits = new BitArray(n + 1);
for (int i = 0; 2 * i + 3 <= n; i++) {
bits.Set(i, CheckPrimality(2 * i + 3));
}
}
public PrimeDictionary(IEnumerable<int> primes) {
bits = new BitArray(primes.Max());
foreach(var prime in primes.Where(p => p != 2)) {
bits.Set((prime - 3) / 2, true);
}
}
public bool IsPrime(int k) {
if (k == 2) {
return true;
}
if (k % 2 == 0) {
return false;
}
return bits[(k - 3) / 2];
}
}
물론의 정의를 지정해야합니다 CheckPrimality.
가장 빠른 방법 중 하나는 내가 만든 방법이라고 생각합니다.
void prime(long long int number) {
// Establishing Variables
long long int i = 5;
int w = 2;
const long long int lim = sqrt(number);
// Gets 2 and 3 out of the way
if (number == 1) { cout << number << " is hard to classify. \n"; return; }
if (number == 2) { cout << number << " is Prime. \n"; return; }
if (number == 3) { cout << number << " is Prime. \n"; return; }
// Tests Odd Ball Factors
if (number % 2 == 0) { cout << number << " is not Prime. \n"; return; }
if (number % 3 == 0) { cout << number << " is not Prime. \n"; return; }
while (i <= lim) {
if (number % i == 0) { cout << number << " is not Prime. \n"; return; }
// Tests Number
i = i + w; // Increments number
w = 6 - i; // We already tested 2 and 3
// So this removes testing multepules of this
}
cout << number << " is Prime. \n"; return;
}
public static boolean isPrime(int number) {
if(number < 2)
return false;
else if(number == 2 || number == 3)
return true;
else {
for(int i=2;i<=number/2;i++)
if(number%i == 0)
return false;
else if(i==number/2)
return true;
}
return false;
}
소수의 첫 번째 규칙 : 2로 나눈 경우 정수 또는 정수와 같습니다. 소수가 아닙니다.
모든 컴퓨터 언어를 사용하는 가장 빠른 방법은 수학이 아닌 문자열을 사용하여 형식을 일치시키는 것입니다. 문자열로 된 Float에서 DOT를 일치시킵니다.
- 2로 나눕니다. n = n / 2
- 이것을 문자열로 변환하십시오. n = string (n)
- 만약 "." n : {printf "예, 프라임입니다!"
}
'programing tip' 카테고리의 다른 글
| 파이 명령 출력을 티로 출력하지만 명령의 종료 코드도 저장합니다 (0) | 2020.06.14 |
|---|---|
| 이동하는 생성자 (0) | 2020.06.14 |
| 열거 형에서 임의의 값을 선택 하시겠습니까? (0) | 2020.06.14 |
| 지도 변환 (0) | 2020.06.14 |
| TabControl에서 TabPage를 숨기는 방법 (0) | 2020.06.14 |