Algorithmus, um die Anzahl der Teiler einer gegebenen Zahl zu berechnen

Question

Was wäre die optimale Algorithmus (Performance-weise), um die Anzahl der Teiler einer bestimmten Zahl zu berechnen?

Es wird groß sein, wenn Sie Pseudo-Code oder einen Link zu einem gewissen Beispiel bieten könnten.

EDIT: Alle Antworten waren sehr hilfreich, danke. Ich bin das Sieb des Atkin Implementierung und dann etwas, das ich werde verwenden, ähnlich wie Jonathan Leffler angegeben. Der Link gepostet von Justin Bozonier hat weitere Informationen darüber, was ich wollte.

Answer 1

Dmitriy ist richtig, dass Sie das Sieb des Atkin wollen würden die prime Liste zu generieren, aber ich glaube nicht, dass die Pflege der gesamten Ausgabe nimmt. Jetzt, wo Sie eine Liste von Primzahlen haben Sie benötigen, um zu sehen, wie viele dieser Primzahlen als Divisor wirken (und wie oft).

Hier einige Python für die algo Schau mal hier und „Betreff suchen: Mathe - Notwendigkeit Teilern Algorithmus“. Zählen Sie die Anzahl der Elemente in der Liste, anstatt sie jedoch zurück.

Hier ist ein Dr. Math die erklärt, was genau es ist, müssen Sie tun mathematisch.

Im Wesentlichen läuft es nach unten zu, wenn Ihre Nummer n ist:
 n = a^x * b^y * c^z
(Wobei a, b und c sind Ns Primteilern und x, y und z die Anzahl der Male, dass Divisor wiederholt wird) dann ist die Gesamtzahl für alle der Teilern ist:
(x + 1) * (y + 1) * (z + 1).

Edit: Übrigens, zu finden a, b, c, etc. Sie tun wollen, werden zu dem, was zu einem gierigen algo beträgt, wenn ich das richtig bin zu verstehen. Beginnen Sie mit Ihrem größten Primdivisor und multipliziert es mit sich, bis eine weitere Multiplikation überschreiten würde die Zahl n. Gehen Sie dann auf den nächst niedrigeren Faktor und mal die vorherige prime ^ Anzahl, wie oft es durch die aktuelle prime multipliziert wurde und halten durch die Primzahl multipliziert wird, bis der nächste wird mehr als n ... etc. Verfolgen Sie die Anzahl der Sie multiplizieren die Teilern zusammen und über diese Zahlen in die Formel anwenden.

Nicht 100% sicher über meine algo Beschreibung aber wenn das nicht es ist, es ist etwas ähnlich.

Answer 2

Es gibt eine Los mehr Techniken zu Factoring als das Sieb des Atkin. Zum Beispiel nehmen wir an 5893. Nun seine sqrt 76.76 ist Faktor wollen ... Jetzt werden wir versuchen, 5893 als Produkt der Quadrate zu schreiben. Well (77 * 77 bis 5893) = 36, 6 quadriert wird, so 5893 = 77 * 77-6 * 6 = (77 + 6) (77-6) = 83 * 71. Wenn das nicht gearbeitet hatte, würden wir geschaut haben, ob 78 * 78-5893 war ein perfekter Platz. Und so weiter. Mit dieser Technik können testen Sie schnell für Faktoren in der Nähe der Quadratwurzel von n viel schneller als von den einzelnen Primzahlen zu testen. Wenn Sie diese Technik für den Ausschluß aus großen Primzahlen mit einem Sieb kombinieren, werden Sie ein viel besseres Factoring Verfahren haben als mit dem Sieb allein.

Und das ist nur eine von einer Vielzahl von Techniken, die entwickelt wurden. Dies ist ein ziemlich einfacher. Es würde Sie eine lange Zeit, sagen wir, genug Zahlentheorie zu lernen, die Factoring-Techniken auf Basis elliptischer Kurven zu verstehen. (Ich weiß, dass sie existieren. Ich verstehe sie nicht.)

Deshalb, wenn Sie mit kleinen ganzen Zahlen zu tun hat, würde ich versuchen, dieses Problem nicht selbst zu lösen. Stattdessen würde ich versuchen, einen Weg zu finden, so etwas wie die PARI verwenden Bibliothek, die bereits eine hocheffiziente Lösung implementiert hat. Damit kann ich eine zufällige 40-stellige Nummer wie 124321342332143213122323434312213424231341 in etwa 0,05 Sekunden Faktor. (Die Faktorisierung, falls Sie sich gefragt, ist 29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. Ich bin sehr zuversichtlich, dass es ist nicht diesen heraus das Sieb von Atkin mit ...)

Answer 3

@Yasky

Ihre Teilerfunktion hat einen Fehler, dass es nicht richtig für perfekte Quadrate funktioniert.

Versuchen:

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;
}

Answer 4

Ich bin nicht einverstanden, dass das Sieb des Atkin ist der Weg zu gehen, weil es leicht länger dauern könnte jede Zahl in [1, n] für primality zu überprüfen, als wäre es die Anzahl von Divisionen zu reduzieren.

Hier ist ein Code, der, wenn auch etwas hackier, in der Regel viel schneller:

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)

ps Das funktioniert Python Code, um dieses Problem zu lösen.

Answer 5

Diese interessante Frage ist viel schwieriger, als es aussieht, und es wird nicht beantwortet. Die Frage lässt sich in zwei sehr unterschiedliche Fragen berücksichtigt werden.

1 gegeben N, finden Sie die Liste L von Ns Primfaktoren

2 gegeben L berechnet Anzahl von einzigartigen Kombinationen

Alle Antworten, die ich bisher auf # 1 beziehen sich sehen und nicht zu erwähnen nicht lenkbar für enorme Zahlen. Für mittlere Größe N, auch 64-Bit-Zahlen ist es leicht; für enormen N kann das Faktorisierungsproblem nehmen „für immer“. Public-Key-Verschlüsselung hängt davon ab.

Frage 2 braucht mehr Diskussion. Wenn L nur eindeutige Zahlen enthält, ist es eine einfache Berechnung der Kombination Formel für die Wahl k Objekte aus n Elementen verwenden. Eigentlich müssen Sie aus der Anwendung der Formel die Ergebnisse zusammenzufassen, während k variiert von 1 bis sizeof (L). Allerdings wird L in der Regel mehrere Vorkommen von mehreren Primzahlen enthalten. Zum Beispiel L = {2,2,2,3,3,5} ist die Faktorisierung von N = 360. Nun ist dieses Problem sehr schwierig ist!

Neuformulierung # 2, gegeben Sammlung C enthalten k Elemente, so dass Punkt A hat eine ‚Duplikate und Punkt b hat b‘ Duplikate etc., wie viele einzigartige Kombinationen von 1 bis k-1 Produkte gibt es? Beispiel: {2}, {2,2}, {2,2,2}, {2,3}, {2,2,3,3} muss jeweils einmal vorkommen und nur einmal, wenn L = {2,2 , 2,3,3,5}. Jede solche einzigartige Unter Sammlung ist ein einzigartigen Teiler von N durch die Elemente in der Untersammlung multipliziert wird.

Answer 6

Eine Antwort auf Ihre Frage hängt stark von der Größe der ganzen Zahl. Verfahren für eine kleine Anzahl, z.B. weniger als 100 Bit, und für die Zahlen bis 1000 Bit (wie in der Kryptographie verwendet) sind völlig verschieden.

• allgemeine Übersicht: http://en.wikipedia.org/wiki/Divisor_function

• Werte für kleine n und einige nützliche Hinweise: A000005: d (n) (auch genannt tau (n) oder sigma_0 (n)), die Anzahl von Divisoren n.

• reales Beispiel: Faktorisierung von ganzen Zahlen

Answer 7

Hier ist ein straight forward O (sqrt (n)) Algorithmus. Ich verwendet, um dieses Projekt euler

lösen

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  

Answer 8

nur eine Zeile
Ich habe sehr carefuly darüber nachgedacht, Ihre Frage, und ich habe versucht, eine hocheffiziente und performant Stück Code zu schreiben Um alle Teiler einer gegebenen Anzahl auf dem Bildschirm drucken müssen wir nur eine Zeile Code! (Verwenden Sie die Option -std = c99 während über gcc kompilieren)

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

für Zahlen von Teilern zu finden, können Sie die folgende verwenden sehr sehr schnelle Funktion (Arbeit richtig für alle Integer-Zahl außer 1 und 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

oder wenn Sie behandeln bestimmte Anzahl als Divisor (Arbeit richtig für alle Integer-Zahl außer 1 und 2)

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

Hinweis: zwei oben genannten Funktionen korrekt funktioniert für alle positive ganze Zahl außer Nummer 1 und 2 so ist es funktional für alle Zahlen, die größer als 2 aber wenn Sie benötigen 1 und 2 abdecken, können Sie eine der folgenden Funktionen (etwas langsamer)

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;
}

oder

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;
}

small is beautiful:)

Answer 9

Das Sieb von Atkin ist eine optimierte Version des Sieb des Eratosthenes, die bis zu einer bestimmten ganzzahligen alle Primzahlen gibt. Sie sollten dies der Lage sein, für weitere Informationen an Google.

Sobald Sie diese Liste haben, ist es eine einfache Sache, Ihre Nummer durch jede Primzahl zu teilen, um zu sehen, ob es eine genaue Divisor ist (das heißt, Rest Null ist).

Die grundlegenden Schritte, um die Teilern für eine Anzahl (n) die Berechnung ist [dieser Pseudo-Code aus echtem Code umgewandelt wird, so hoffe ich, ich habe keine Fehler eingeführt]:

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

Answer 10

Sie könnten versuchen diese. Es ist ein bisschen hackish, aber es ist ziemlich schnell.

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

Answer 11

Wenn Sie die Primfaktorzerlegung haben, gibt es eine Möglichkeit, die Anzahl der Teiler zu finden. Fügen Sie ein zu jedem der Exponenten auf jedem einzelnen Faktor und dann die Exponenten multiplizieren zusammen.

Zum Beispiel: 36 Primfaktorzerlegung: 2 ^ 2 * 3 ^ 2 Divisoren: 1, 2, 3, 4, 6, 9, 12, 18, 36 Anzahl der Teiler: 9

ein In den einzelnen Exponenten 2 ^ 3 * 3 ^ 3 Multiply Exponenten: 3 * 3 = 9

Answer 12

Bevor Sie zu einer Lösung verpflichten bedenken, dass der Sieve Ansatz nicht eine gute Antwort im typischen Fall sein könnte.

Vor einiger Zeit gibt es eine Primzahl Frage war und ich eine Zeittest haben - für 32-Bit-Integer zumindest zu bestimmen, ob es war prime war langsamer als rohe Gewalt. Es gibt zwei Faktoren los:

1) Während ein Mensch eine Weile dauert, auf dem Computer eine Division sind sie sehr schnell zu tun - ähnlich wie die Kosten für die Antwort aufzuzublicken

.

2) Wenn Sie nicht über eine erstklassige Tabelle haben können eine Schleife bilden, die vollständig in dem L1-Cache läuft. Dies macht es schneller.

Answer 13

Dies ist eine effiziente Lösung:

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

Answer 14

Divisoren tun etwas Spektakuläres: sie teilen vollständig. Wenn Sie die Anzahl der Teiler für eine Zahl, n überprüfen mögen, es ist eindeutig überflüssig das gesamte Spektrum zu überbrücken, 1...n. Ich habe keine in eingehenden Untersuchungen für diese getan, aber ich gelöst Projekt Euler Problem 12 auf Dreieckszahl . Meine Lösung für den größer als 500 Teilern Test lief für 309.504 Mikrosekunden (~ 0,3s). Ich schrieb diese Divisor-Funktion für die Lösung.

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;
}

Zu jedem Algorithmus gibt es eine Schwachstelle. Ich dachte, das war schwach gegen Primzahlen. Aber da Dreieckszahlen werden nicht gedruckt, diente es seinen Zweck einwandfrei. Aus meiner Profilierung, ich denke, es ist ziemlich gut gemacht.

Frohe Feiertage.

Answer 15

Sie möchten das Sieb des Atkin, hier beschrieben: http://en.wikipedia.org/wiki / Sieve_of_Atkin

Answer 16

die Primzahl Methode ist hier sehr klar. P [] ist eine Liste der Primzahl kleiner als oder gleich dem Quadrat = 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  .

Answer 17

Die Zahlentheorie Lehrbücher nennen die Divisor-Zählfunktion tau. Die erste interessante Tatsache ist, dass es multiplikativ, dh. τ (ab) = τ (a) τ (b), wenn a und b haben keinen gemeinsamen Faktor. . (Beweis: jedes Paar von Teilern von a und b gibt einen deutlichen Teiler von ab)

beachten Nun, da für p eine Primzahl, τ (p ** k) = k + 1 (die Potenzen von p). So können Sie leicht τ (n) aus der Faktorisierung berechnen.

Allerdings Faktorisierung große Zahlen können langsam sein (die Sicherheit von RSA crytopraphy hängt vom Produkt aus zwei großen Primzahlen schwer zu faktorisieren ist). Das legt nahe, diese optimierten Algorithmus

1. -Test, wenn die Zahl eine Primzahl ist (fast)
2. Wenn ja, gibt 2
3. Andernfalls faktorisieren die Anzahl (langsam, wenn mehrere große Primfaktoren)
4. Compute τ (n) aus der Faktorisierung

Answer 18

Das folgende ist ein C-Programm die Anzahl der Teiler einer gegebenen Zahl zu finden.

Die Komplexität des obigen Algorithmus ist O (sqrt (n)).

Dieser Algorithmus funktioniert richtig für die Nummer, die wie auch die Zahlen Quadratzahl sind, die nicht perfekt quadratisch.

Beachten Sie, dass die Obergrenze der Schleife auf die Quadratwurzel der Zahl festgelegt wird, um den Algorithmus zu haben, am effizientesten ist.

Beachten Sie, dass die Obergrenze in einer separaten Variable speichert auch die Zeit speichert, sollten Sie die Funktion sqrt im Bedingungsteil der for-Schleife nicht nennen, dies spart auch Ihre Rechenzeit.

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

Anstelle der oben für die Schleife Sie auch die folgende Schleife verwenden können, die eine effiziente noch mehr ist, da dies die Notwendigkeit entfernt die Quadratwurzel der Anzahl zu finden.

for(i=2;i*i<=n;i++)
{
    ...
}

Answer 19

Hier ist eine Funktion, die ich geschrieben habe. es ist schlimmste Zeit Komplexität O (sqrt (n)), beste Zeit, auf der anderen Seite ist O (log (n)). Es gibt Ihnen alle Primteilern zusammen mit der Anzahl seiner Vorkommen.

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;
}

Answer 20

Dies ist die einfachste Art und Weise die Anzahl divissors der Berechnung:

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

    }
}

Answer 21

@Kendall

teste ich Ihren Code und einige Verbesserungen gemacht, jetzt ist es sogar noch schneller. Ich habe auch mit @ هومن جاویدپور Code getestet, ist dies auch schneller als sein Code.

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;
}

Answer 22

Ist das nicht nur eine Frage der Anzahl Factoring - Bestimmung aller Faktoren der Zahl? Sie können dann entscheiden, ob Sie alle Kombinationen von einem oder mehreren Faktoren benötigen.

So ein möglicher Algorithmus wäre:

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

Es ist dann an Sie, die Faktoren zu kombinieren, um den Rest der Antwort zu bestimmen.

Answer 23

Das ist etwas, was ich mit aufkommen, basierend auf Justin Antwort. Es könnte einige Optimierung erfordern.

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

Answer 24

Ich denke, das ist, was Sie suchen for.I tut genau das, was Sie gefragt. Kopieren und einfügen es in Notepad.Save als * .bat.Run.Enter Number.Multiply den Prozess von 2 und das ist die Anzahl der divisors.I gemacht, dass absichtlich so das es die Teilern bestimmt schneller:

Pls beachten Sie, dass ein CMD varriable kippen Stützwerte über 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

Answer 25

Ich denke, das wird man auch so präzise praktisch sein

script.pyton

>>>factors=[ x for x in range (1,n+1) if n%x==0] print len(factors)

Answer 26

Versuchen Sie etwas in dieser Richtung:

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;
}

Answer 27

Sie können Primzahlen bis zur sqaure Wurzel des maximal möglichen N vorauszuzuberechnen und die Exponenten eines jeden Primfaktor einer Zahl berechnen. Die Anzahl der Teiler von n (n = p1 p2 ^ a ^ b ^ p3 ... c) (a + 1) (b + 1) (c + 1), da es das gleiche ist, wie die Art und Weise Zählung der prime kombinieren diese Faktoren Zahlen (und dies wird die Anzahl der Teiler zählen). Das ist sehr schnell, wenn Sie die Primzahlen precompute

Ausführlichere Informationen zu dieser Methode:

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;
    }
}

Answer 28

Ich weiß nicht die effizienteste Methode, aber ich würde wie folgt vor:

• Erstellen Sie eine Tabelle der Primzahlen als alle Primzahlen weniger zu finden oder gleich der Quadratwurzel aus der Anzahl (Persönlich würde ich das Sieb des Atkin verwenden)
• Count alle Primzahlen kleiner oder gleich der Quadratwurzel aus der Anzahl und multiplizieren die durch zwei. Wenn die Quadratwurzel der Zahl eine ganze Zahl ist, dann Subtrahieren eines von der Zählvariable.

Sollte funktionieren \ o /

Wenn Sie brauchen, kann ich etwas morgen in C-Code zu demonstrieren.