프라임을 검출하는 방법

Question

나는 무언가가 참임을 보여주는 많은 이진 연산이 있다는 것을 알고있다. 예를 들어 숫자가 2의 거듭 제곱인지 아니면 다른 것이 있는지를 보여줄 수있는 몇 가지 이론이나 특별한 이진법이 있음을 보여줄 수있다. 초기?

Answer 1

숫자가 소수인지 확인하는 것은 그리 쉽지 않습니다!

돌연변이가 PRIMES is in P 인이 기사를 읽으십시오 : http://www.ams.org/notices/200305/fea-bornemann.pdf 이것은 실제로 얼마나 어려운 문제인지에 대한 아이디어를 제공합니다. 간단한 '바이너리 방식'이 유명해질 것을 발견하면, 한마디로 http://members.cox.net/mathmistakes/primes.htm

:

이 뉴스 기사는 쉽게 읽기 수 있습니다!

Answer 2

일반적으로 check입니다.

Answer 3

소수를 찾는 시브 (Sieve) 알고리즘의 좋은 예를 보려면이 위키 백과 페이지를 확인하십시오. (같은 페이지의 하단에 감동) 소수를 찾기위한 재미있는 방법

한

Sieve of Eratosthenes

하고, 오일러 체는 그것을 조금 속도가 빨라집니다.

Answer 4

2의 마력과 소수 사이에는 실제로 큰 차이가 있습니다.
당신은 숫자 표현의 우리의 시스템을 살펴 보겠습니다 경우 1243 = 1 * 10 ³ + 2 * 10 ² + 4 * 10 ¹ + 3 * 10 ⁰
그것은 꽤 쉽게 숫자를 10으로 나눌 수있는시기 (최하위 자리가 0 임) 또는 10의 거듭 제곱을 결정하십시오 (모든 최하위 자리가 0이고 최고 자리수가 1 인 경우 또는 모든 자리수의 합이 1 일 때). 1,243 = 1 * 2 ¹⁰ + 0 * 2 ⁹ + 0 * 2 ⁸ + 1 * 2 ⁷ + 1 * 2 ⁶ + 0 * 2 ⁵ 바이너리 용
동일한 + 1 * 2 ⁴ + 1 * 2 ³ + 0 * 2 ² + 1 * 2 ¹ + 1 * 2 ⁰ 참고 번호 (2)에 의해 분할 될 수 있는지 확인하기 위해 숫자를 확인할 수
또는 10의 숫자 표현과 같은 방식으로 2의 거듭 제곱입니다.

이제 다른 숫자 표현 시스템을 고려해보십시오.나는 로마 숫자는 몇 가지 흥미로운 특성을 가져야한다 생각하지만, 같은에서 당신이 아마 관심이 : 1243 = 2 ⁰ * 3 ⁰ * 5 ⁰ * 7 ⁰ * 11 ¹ * 13 ^{0* 17 * 19 0} * 0 23 0 ^{* 29 * 31 0} * 0 37 0 ^{* 41 * 43 0},586 3,491,524,963,210 0 * 47 ⁰ * 53 ⁰ * 59 ⁰ * 61 ⁰ * 67 ⁰ * 71 ⁰ * 73 ⁰ * 79 ⁰ * 83 ⁰ * 89 0 * 97 *^{0 101 0* 103 * 107 0 0 * 0 109 01,230,618,695,631,163,888 98,853,210 * 113 1 = 11 1 * 113 1 = 0000100000 ...] _{프라임 기반}
즉 number는 소수의 지수의 곱으로 부호화됩니다. 이러한 시스템은 비트 단위 또는 소수 단위보다 다른 소수 단위 관련 검사를 훨씬 쉽게 수행 할 수 있습니다.}

P. 가중치가있는 시스템은 합계와 차를 쉽게 계산할 수있는 방법을 제공하지만 전원 공급 제품을 사용하는 시스템은 곱셈과 나눗셈을 단순화합니다.

Answer 5

bool isPrime(int number){ 

    if(number < 2) return false; 
    if(number == 2) return true; 
    if(number % 2 == 0) return false; 
    for(int i=3; (i*i)<=number; i+=2){ 
     if(number % i == 0) return false; 
    } 
    return true; 

} 

알림. 입력이 10^9 이상이면 느려질 것입니다.