주어진 숫자의 제수 수를 계산하는 알고리즘
https://stackoverflow.com/questions/110344
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
주어진 숫자의 제수 수를 계산하는 가장 최적의 알고리즘(성능 측면)은 무엇입니까?
의사 코드나 몇 가지 예에 대한 링크를 제공할 수 있다면 좋을 것입니다.
편집하다:모든 답변이 매우 도움이 되었습니다. 감사합니다.나는 Sieve of Atkin을 구현하고 Jonathan Leffler가 지적한 것과 유사한 것을 사용할 것입니다.Justin Bozonier가 게시한 링크에는 내가 원하는 것에 대한 추가 정보가 있습니다.
해결책
Dmitriy는 Sieve of Atkin이 주요 목록을 생성하기를 원할 것이라는 점에서 옳습니다. 그러나 그것이 전체 문제를 해결한다고는 생각하지 않습니다.이제 소수 목록이 있으므로 소수 중 몇 개가 제수 역할을 하는지(그리고 얼마나 자주) 확인해야 합니다.
여기 알고(algo)를 위한 파이썬이 있습니다. 이봐 그리고 "제목:수학 - 제수 알고리즘이 필요합니다."그러나 항목을 반환하는 대신 목록에 있는 항목 수를 세어보세요.
여기 박사가 있습니다.수학 수학적으로 수행해야 하는 작업이 정확히 무엇인지 설명합니다.
본질적으로 그것은 귀하의 전화 번호로 귀결됩니다. n 이다:
n = a^x * b^y * c^z
(여기서 A, B 및 C는 N의 프라임 디바이저이고 X, Y 및 Z는 디바이저가 반복되는 횟수입니다) 모든 제수의 총 수는 다음과 같습니다.
(x + 1) * (y + 1) * (z + 1).
편집하다:그런데, a, b, c 등을 찾으려면 내가 이것을 올바르게 이해하고 있다면 탐욕스러운 알고에 해당하는 작업을 수행하고 싶을 것입니다.가장 큰 소수로 시작하여 추가 곱셈이 숫자 n을 초과할 때까지 그 자체로 곱하십시오.그런 다음 다음으로 가장 낮은 요소로 이동하여 이전 소수에 현재 소수를 곱한 횟수를 곱하고 다음 소수가 n을 초과할 때까지 소수를 계속 곱합니다.등.제수를 곱한 횟수를 기록하고 그 숫자를 위 공식에 적용하세요.
내 알고 설명에 대해 100% 확신할 수는 없지만 그렇지 않다면 비슷한 것입니다.
다른 팁
있다 많은 Atkin의 체보다 더 많은 인수분해 기술이 있습니다.예를 들어 5893을 인수분해한다고 가정해 보겠습니다.sqrt는 76.76입니다...이제 우리는 5893을 제곱의 곱으로 써보겠습니다.(77*77 - 5893) = 36은 6의 제곱이므로 5893 = 77*77 - 6*6 = (77 + 6)(77-6) = 83*71입니다.만약 이것이 작동하지 않았다면 우리는 78*78 - 5893이 완전제곱수인지 살펴봤을 것입니다.등등.이 기술을 사용하면 개별 소수를 테스트하는 것보다 훨씬 빠르게 n의 제곱근 근처의 요인을 빠르게 테스트할 수 있습니다.큰 소수를 배제하기 위해 이 기술을 체와 결합하면 체만 사용하는 것보다 훨씬 더 나은 인수분해 방법을 갖게 됩니다.
그리고 이것은 개발된 수많은 기술 중 하나일 뿐입니다.이것은 매우 간단한 것입니다.예를 들어 타원 곡선을 기반으로 한 인수분해 기술을 이해하기에 충분한 정수론을 배우려면 오랜 시간이 걸릴 것입니다.(나는 그들이 존재한다는 것을 안다.나는 그들을 이해하지 못한다.)
따라서 작은 정수를 다루지 않는 한 나는 그 문제를 직접 해결하려고 시도하지 않을 것입니다.대신에 나는 다음과 같은 것을 사용하는 방법을 찾으려고 노력할 것입니다. 파리 이미 매우 효율적인 솔루션이 구현된 라이브러리입니다.이를 통해 약 0.05초 만에 124321342332143213122323434312213424231341과 같은 임의의 40자리 숫자를 인수분해할 수 있습니다.(궁금하시겠지만, 인수분해는 29*439*1321*157907*284749*33843676813*4857795469949입니다.나는 Atkin의 체를 사용하여 이것을 알아 내지 못했다고 확신합니다 ...)
@야스키
제수 함수에는 완전제곱수에 대해 올바르게 작동하지 않는다는 버그가 있습니다.
노력하다:
int divisors(int x) {
int limit = x;
int numberOfDivisors = 0;
if (x == 1) return 1;
for (int i = 1; i < limit; ++i) {
if (x % i == 0) {
limit = x / i;
if (limit != i) {
numberOfDivisors++;
}
numberOfDivisors++;
}
}
return numberOfDivisors;
}
나는 Atkin의 체를 사용하는 것이 좋은 방법이라는 데 동의하지 않습니다. 왜냐하면 [1,n]의 모든 숫자를 소수로 확인하는 것이 나눗셈으로 숫자를 줄이는 것보다 시간이 더 오래 걸릴 수 있기 때문입니다.
약간 해킹되기는 하지만 일반적으로 훨씬 빠른 코드는 다음과 같습니다.
import operator
# A slightly efficient superset of primes.
def PrimesPlus():
yield 2
yield 3
i = 5
while True:
yield i
if i % 6 == 1:
i += 2
i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
d = {}
primes = PrimesPlus()
for p in primes:
while n % p == 0:
n /= p
d[p] = d.setdefault(p, 0) + 1
if n == 1:
return d
def NumberOfDivisors(n):
d = GetPrimeDecomp(n)
powers_plus = map(lambda x: x+1, d.values())
return reduce(operator.mul, powers_plus, 1)
추신 이 문제를 해결하기 위해 Python 코드를 사용하고 있습니다.
이 흥미로운 질문은 보기보다 훨씬 어렵고 아직까지 답변을 얻지 못했습니다.이 질문은 매우 다른 두 가지 질문으로 나누어질 수 있습니다.
N이 주어지면 1, N의 소인수 목록 L을 찾습니다.
2 주어진 L, 고유 조합 수 계산
지금까지 내가 본 모든 답변은 #1을 참조하고 있으며 엄청난 숫자에 대해서는 다루기 어렵다는 점을 언급하지 못했습니다.적당한 크기의 N, 심지어 64비트 숫자의 경우에도 쉽습니다.거대한 N의 경우 인수분해 문제는 "영원히" 걸릴 수 있습니다.공개 키 암호화는 이에 따라 달라집니다.
질문 #2에는 더 많은 논의가 필요합니다.L에 고유한 숫자만 포함되어 있는 경우 n개 항목에서 k개 객체를 선택하는 조합식을 사용한 간단한 계산입니다.실제로 k를 1에서 sizeof(L)까지 변경하면서 공식을 적용한 결과를 합산해야 합니다.그러나 L에는 일반적으로 여러 소수가 여러 번 포함됩니다.예를 들어, L = {2,2,2,3,3,5}는 N = 360의 인수분해입니다.이제 이 문제는 꽤 어렵습니다!
#2를 다시 말하면, k 항목을 포함하는 컬렉션 C가 주어지고 항목 a에는 a' 중복이 있고 항목 b에는 b' 중복이 있는 등입니다.1~k-1 항목의 고유한 조합은 몇 개입니까?예를 들어, {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3}은 각각 한 번 발생해야 하며 L = {2,2인 경우 한 번만 발생해야 합니다. ,2,3,3,5}.각각의 고유한 하위 컬렉션은 하위 컬렉션의 항목을 곱하여 N의 고유한 제수입니다.
귀하의 질문에 대한 대답은 정수의 크기에 따라 크게 달라집니다.작은 숫자에 대한 방법(예:100비트 미만이고 숫자의 경우 ~1000비트(예: 암호화에 사용됨)는 완전히 다릅니다.
작은 가치
n그리고 몇 가지 유용한 참고자료: A000005:d(n) (tau(n) 또는 sigma_0(n)이라고도 함), n의 제수 수입니다.실제 예: 정수의 인수분해
다음은 간단한 O(sqrt(n)) 알고리즘입니다.나는 이것을 해결하기 위해 사용했다 프로젝트 오일러
def divisors(n):
count=2 # accounts for 'n' and '1'
i=2
while(i**2 < n):
if(n%i==0):
count+=2
i+=1
count+=(1 if i**2==n else 0)
return count
한줄만요
나는 당신의 질문에 대해 매우 조심스럽게 생각했고, 화면에 주어진 숫자의 모든 디바이저를 인쇄하기 위해 매우 효율적이고 성능이 좋은 코드를 작성하려고 노력했습니다. 단 한 줄의 코드 만 필요합니다!(gcc를 통해 컴파일하는 동안 -std=c99 옵션 사용)
for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number
제수 수를 찾으려면 다음과 같은 매우 빠른 기능을 사용할 수 있습니다(1과 2를 제외한 모든 정수에 대해 올바르게 작동함).
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return counter;
}
또는 주어진 숫자를 제수로 처리하는 경우(1과 2를 제외한 모든 정수에 대해 올바르게 작동)
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
return ++counter;
}
참고 : 위의 두 기능은 번호 1 및 2를 제외한 모든 양의 정수 번호에 대해 올바르게 작동하므로 2보다 큰 모든 숫자에 대해 기능적이지만 1과 2를 다루어야하는 경우 다음 기능 중 하나를 사용할 수 있습니다 (작은 작은 것입니다. 느린다)
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
if (n==2 || n==1)
{
return counter;
}
return ++counter;
}
또는
int number_of_divisors(int n)
{
int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
return ++counter;
}
작은 것이 아름답다 :)
앳킨의 체는 주어진 정수까지의 모든 소수를 제공하는 에라토스테네스의 체의 최적화된 버전입니다.자세한 내용은 구글링을 해봐야 알 수 있을 것 같습니다.
해당 목록이 있으면 숫자를 각 소수로 나누어 그것이 정확한 제수인지(즉, 나머지가 0인지) 확인하는 것은 간단합니다.
숫자(n)에 대한 제수를 계산하는 기본 단계는 다음과 같습니다. [이것은 실제 코드에서 변환된 의사코드이므로 오류가 발생하지 않기를 바랍니다]:
for z in 1..n:
prime[z] = false
prime[2] = true;
prime[3] = true;
for x in 1..sqrt(n):
xx = x * x
for y in 1..sqrt(n):
yy = y * y
z = 4*xx+yy
if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
prime[z] = not prime[z]
z = z-xx
if (z <= n) and (z mod 12 == 7):
prime[z] = not prime[z]
z = z-yy-yy
if (z <= n) and (x > y) and (z mod 12 == 11):
prime[z] = not prime[z]
for z in 5..sqrt(n):
if prime[z]:
zz = z*z
x = zz
while x <= limit:
prime[x] = false
x = x + zz
for z in 2,3,5..n:
if prime[z]:
if n modulo z == 0 then print z
이것을 시도해 볼 수도 있습니다.약간 해킹적이지만 상당히 빠릅니다.
def factors(n):
for x in xrange(2,n):
if n%x == 0:
return (x,) + factors(n/x)
return (n,1)
소인수분해를 하면 제수의 수를 구하는 방법이 있습니다.각 개별 요소의 각 지수에 1을 더한 다음 지수를 함께 곱합니다.
예를 들어:36 주요 요인화 :2^2*3^2 디바이저 :1, 2, 2, 3, 4, 6, 9, 12, 18, 36 디바이저 수 :9
각 지수에 하나를 추가하여 2^3*3^3 지수를 곱하십시오.3*3 = 9
솔루션을 결정하기 전에 Sieve 접근 방식이 일반적인 경우에는 좋은 대답이 아닐 수도 있다는 점을 고려하십시오.
얼마 전에 소수에 관한 질문이 있었고 저는 시간 테스트를 했습니다. 적어도 32비트 정수에 대해 그것이 소수인지 결정하는 것이 무차별 대입보다 느렸습니다.두 가지 요인이 진행되고 있습니다.
1) 인간이 나눗셈을 하는 데는 시간이 좀 걸리지만 컴퓨터에서는 매우 빠릅니다. 이는 답을 찾는 데 드는 비용과 유사합니다.
2) 프라임 테이블이 없으면 L1 캐시에서 완전히 실행되는 루프를 만들 수 있습니다.이렇게 하면 속도가 빨라집니다.
이는 효율적인 솔루션입니다.
#include <iostream>
int main() {
int num = 20;
int numberOfDivisors = 1;
for (int i = 2; i <= num; i++)
{
int exponent = 0;
while (num % i == 0) {
exponent++;
num /= i;
}
numberOfDivisors *= (exponent+1);
}
std::cout << numberOfDivisors << std::endl;
return 0;
}
제수는 놀라운 일을 합니다:그들은 완전히 나누어집니다.숫자의 제수 개수를 확인하고 싶다면, n, 전체 스펙트럼을 포괄하는 것은 분명히 중복됩니다. 1...n.이에 대해 깊이 조사한 적은 없지만 해결했습니다. 프로젝트 오일러의 삼각수 문제 12.나의 솔루션 500보다 큰 약수 테스트는 309504마이크로초(~0.3초) 동안 실행되었습니다.나는 솔루션을 위해 이 제수 함수를 작성했습니다.
int divisors (int x) {
int limit = x;
int numberOfDivisors = 1;
for (int i(0); i < limit; ++i) {
if (x % i == 0) {
limit = x / i;
numberOfDivisors++;
}
}
return numberOfDivisors * 2;
}
모든 알고리즘에는 약점이 있습니다.소수에 약하다고 생각했어요.그러나 삼각수는 인쇄되지 않았기 때문에 그 목적을 완벽하게 달성했습니다.내 프로필에 따르면 꽤 잘했다고 생각합니다.
즐거운 휴일 보내세요.
당신은 여기에 설명된 앳킨의 체를 원합니다: http://en.wikipedia.org/wiki/Sieve_of_Atkin
소수 방법은 여기에서 매우 명확합니다.P[]는 sq = sqrt(n)보다 작거나 같은 소수의 목록입니다.
for (int i = 0 ; i < size && P[i]<=sq ; i++){
nd = 1;
while(n%P[i]==0){
n/=P[i];
nd++;
}
count*=nd;
if (n==1)break;
}
if (n!=1)count*=2;//the confusing line :D :P .
i will lift the understanding for the reader .
i now look forward to a method more optimized .
정수론 교과서에서는 제수 계산 함수 타우를 호출합니다.첫 번째 흥미로운 사실은 이것이 곱셈이라는 것입니다.τ(ab) = τ(a)τ(b), a와 b가 공통 인수를 갖지 않는 경우.(증거:a와 b의 각 약수 쌍은 ab의 고유한 약수를 제공합니다.
이제 p a 소수에 대해 τ(p**k) = k+1(p의 거듭제곱)에 주목하세요.따라서 인수분해를 통해 τ(n)을 쉽게 계산할 수 있습니다.
그러나 큰 숫자를 인수분해하는 것은 느릴 수 있습니다(RSA 암호화의 보안은 인수분해하기 어려운 두 개의 큰 소수의 곱에 달려 있습니다).이는 최적화된 알고리즘을 제안합니다.
- 숫자가 소수인지 테스트합니다(빠름).
- 그렇다면 2를 반환하세요.
- 그렇지 않으면, 숫자를 인수분해하다 (큰 소인수가 여러 개인 경우 속도가 느림)
- 인수분해로부터 τ(n)을 계산합니다.
다음은 주어진 숫자의 제수 개수를 구하는 C 프로그램입니다.
위 알고리즘의 복잡도는 O(sqrt(n))입니다.
이 알고리즘은 완전제곱수인 숫자와 완전제곱수가 아닌 숫자에 대해 올바르게 작동합니다.
루프의 상한은 알고리즘이 가장 효율적이도록 숫자의 제곱근으로 설정됩니다.
상한값을 별도의 변수에 저장하면 시간도 절약됩니다. for 루프의 조건 섹션에서 sqrt 함수를 호출하면 안 됩니다. 이렇게 하면 계산 시간도 절약됩니다.
#include<stdio.h>
#include<math.h>
int main()
{
int i,n,limit,numberOfDivisors=1;
printf("Enter the number : ");
scanf("%d",&n);
limit=(int)sqrt((double)n);
for(i=2;i<=limit;i++)
if(n%i==0)
{
if(i!=n/i)
numberOfDivisors+=2;
else
numberOfDivisors++;
}
printf("%d\n",numberOfDivisors);
return 0;
}
위의 for 루프 대신 다음 루프를 사용할 수도 있습니다. 이는 숫자의 제곱근을 찾을 필요가 없기 때문에 더욱 효율적입니다.
for(i=2;i*i<=n;i++)
{
...
}
제가 작성한 함수는 다음과 같습니다.최악의 시간 복잡도는 O(sqrt(n))이고, 반면에 가장 좋은 시간은 O(log(n))입니다.그것은 발생 횟수와 함께 모든 소인수를 제공합니다.
public static List<Integer> divisors(n) {
ArrayList<Integer> aList = new ArrayList();
int top_count = (int) Math.round(Math.sqrt(n));
int new_n = n;
for (int i = 2; i <= top_count; i++) {
if (new_n == (new_n / i) * i) {
aList.add(i);
new_n = new_n / i;
top_count = (int) Math.round(Math.sqrt(new_n));
i = 1;
}
}
aList.add(new_n);
return aList;
}
이것은 숫자 제수를 계산하는 가장 기본적인 방법입니다.
class PrintDivisors
{
public static void main(String args[])
{
System.out.println("Enter the number");
// Create Scanner object for taking input
Scanner s=new Scanner(System.in);
// Read an int
int n=s.nextInt();
// Loop from 1 to 'n'
for(int i=1;i<=n;i++)
{
// If remainder is 0 when 'n' is divided by 'i',
if(n%i==0)
{
System.out.print(i+", ");
}
}
// Print [not necessary]
System.out.print("are divisors of "+n);
}
}
@켄달
귀하의 코드를 테스트하고 몇 가지 개선 사항을 적용하여 이제 훨씬 더 빨라졌습니다.또한 @هومن جاویدپور 코드로 테스트했는데 이 코드도 그의 코드보다 빠릅니다.
long long int FindDivisors(long long int n) {
long long int count = 0;
long long int i, m = (long long int)sqrt(n);
for(i = 1;i <= m;i++) {
if(n % i == 0)
count += 2;
}
if(n / m == m && n % m == 0)
count--;
return count;
}
이것은 단지 숫자를 인수분해하는 문제, 즉 숫자의 모든 인수를 결정하는 문제가 아닙니까?그런 다음 하나 이상의 요인 조합이 모두 필요한지 여부를 결정할 수 있습니다.
따라서 가능한 알고리즘 중 하나는 다음과 같습니다.
factor(N)
divisor = first_prime
list_of_factors = { 1 }
while (N > 1)
while (N % divisor == 0)
add divisor to list_of_factors
N /= divisor
divisor = next_prime
return list_of_factors
그런 다음 요소를 결합하여 나머지 답변을 결정하는 것은 귀하에게 달려 있습니다.
이것은 저스틴의 답변을 바탕으로 제가 생각해낸 것입니다.약간의 최적화가 필요할 수 있습니다.
n=int(input())
a=[]
b=[]
def sieve(n):
np = n + 1
s = list(range(np))
s[1] = 0
sqrtn = int(n**0.5)
for i in range(2, sqrtn + 1):
if s[i]:
s[i*i: np: i] = [0] * len(range(i*i, np, i))
return filter(None, s)
k=list(sieve(n))
for i in range(len(k)):
if n%k[i]==0:
a.append(k[i])
a.sort()
for i in range(len(a)):
j=1
while n%(a[i]**j)==0:
j=j+1
b.append(j-1)
nod=1
for i in range(len(b)):
nod=nod*(b[i]+1)
print('no.of divisors of {} = {}'.format(n,nod))
내 생각에는 이것이 당신이 찾고 있는 것 같아요.나는 당신이 요청한 것을 정확히 수행합니다.메모장에 복사하여 붙여넣습니다. *.bat.Run.Number로 저장합니다. 프로세스에 2를 곱하면 이것이 제수 수입니다. 제수를 더 빨리 결정하도록 의도적으로 만들었습니다.
CMD 변수는 999999999 이상의 값을 지원할 수 없습니다.
@echo off
modecon:cols=100 lines=100
:start
title Enter the Number to Determine
cls
echo Determine a number as a product of 2 numbers
echo.
echo Ex1 : C = A * B
echo Ex2 : 8 = 4 * 2
echo.
echo Max Number length is 9
echo.
echo If there is only 1 proces done it
echo means the number is a prime number
echo.
echo Prime numbers take time to determine
echo Number not prime are determined fast
echo.
set /p number=Enter Number :
if %number% GTR 999999999 goto start
echo.
set proces=0
set mindet=0
set procent=0
set B=%Number%
:Determining
set /a mindet=%mindet%+1
if %mindet% GTR %B% goto Results
set /a solution=%number% %%% %mindet%
if %solution% NEQ 0 goto Determining
if %solution% EQU 0 set /a proces=%proces%+1
set /a B=%number% / %mindet%
set /a procent=%mindet%*100/%B%
if %procent% EQU 100 set procent=%procent:~0,3%
if %procent% LSS 100 set procent=%procent:~0,2%
if %procent% LSS 10 set procent=%procent:~0,1%
title Progress : %procent% %%%
if %solution% EQU 0 echo %proces%. %mindet% * %B% = %number%
goto Determining
:Results
title %proces% Results Found
echo.
@pause
goto start
내 생각엔 이게 편리할 뿐만 아니라 정확할 것 같아
script.pyton
>>>factors=[ x for x in range (1,n+1) if n%x==0]
print len(factors)
다음 내용을 따라 시도해 보세요.
int divisors(int myNum) {
int limit = myNum;
int divisorCount = 0;
if (x == 1)
return 1;
for (int i = 1; i < limit; ++i) {
if (myNum % i == 0) {
limit = myNum / i;
if (limit != i)
divisorCount++;
divisorCount++;
}
}
return divisorCount;
}
가능한 최대 N의 제곱근까지 소수를 미리 계산하고 숫자의 모든 소인수의 지수를 계산할 수 있습니다.n (n = p1^a p2^b p3^c...)의 약수의 개수는 (a+1)(b+1)(c+1)입니다. 왜냐하면 소수를 결합하는 방법을 세는 것과 같기 때문입니다. 이 인수의 수(이것은 제수의 수를 계산합니다).소수를 미리 계산하면 매우 빠릅니다.
이 방법에 대한 자세한 정보:
https://mathschallenge.net/library/number/number_of_divisors
https://www.math.upenn.edu/~deturck/m170/wk2/numdivisors.html
http://primes.utm.edu/glossary/xpage/tau.html
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int divisors_count(const vector<int>& primes, int n)
{
int divisors = 1;
for (int i = 0; i < primes.size(); ++i) {
int factor = primes[i];
int factor_exponent = 0;
while (n % factor == 0) {
++factor_exponent;
n /= factor;
}
divisors *= (factor_exponent + 1);
}
if (n > 1)
return 2*divisors; // prime factor > sqrt(MAX_N)
return divisors;
}
int main()
{
const int MAX_N = 1e6;
int max_factor = sqrt(MAX_N);
vector<char> prime(max_factor + 1, true);
for (int i = 3; i <= max_factor; i += 2) {
if (prime[i]) {
for (int j = 3*i; j <= max_factor; j += 2*i) {
prime[j] = false;
}
}
}
vector<int> primes;
primes.reserve(max_factor/2);
primes.push_back(2);
for (int i = 3; i <= max_factor; i += 2) {
if (prime[i]) {
primes.push_back(i);
}
}
int n;
while (cin >> n) {
cout << divisors_count(primes, n) << endl;
}
}
가장 효율적인 방법은 모르지만 다음을 수행합니다.
- 숫자의 제곱근보다 작거나 같은 모든 소수를 찾기 위해 소수 테이블을 만듭니다. (개인적으로는 Atkin의 체를 사용합니다.)
- 숫자의 제곱근보다 작거나 같은 모든 소수의 수를 세고 2를 곱합니다.숫자의 제곱근이 정수이면 카운트 변수에서 1을 뺍니다.
작동해야 합니다 \o/
필요하시면 내일 C로 코딩하여 시연해 드릴 수 있습니다.
