[C++] Conteggio dei divisori

[ilario991]

Salve. Ho realizzato un programma per calcolare tutti i divisori di un numero solo che con gli n che sono circa 10^12 non funziona(va troppo lento).

Testo del problema:

[b]Descrizione del problema[/b]

Sia x un numero intero. Diremo che y è un divisore di x se 1 <= y <= x e il resto della divisione di x per y è uguale a zero.

Si chiede di contare tutti i possibili divisori di un dato numero x.
[b]Dati di input[/b]

Il file di input contiene un intero x (1 <= x <= 10^18). Tutti i divisori primi di x non superano 1000.
[b]Dati di output[/b]

Deve contenere il risultato richiesto dal problema.

Questo è quello che ho scritto io

#include <iostream>
#include <fstream>
#include <vector>
	using namespace std;
	inline int operator % (vector<int>v, unsigned long long k) {
		unsigned long temp = 0;
		while (v.size() != 0) {
			while (temp < k && v.size() != 0) {
				temp = temp * 10 + v[0];
				v.erase(v.begin());
			}
			temp = temp % k;
		}
		return temp;
	}

	int main() {
		ifstream in;
		ofstream out;
		vector<int>v1;
		register unsigned divisore;
		in.open("input.txt");
		if (in.is_open()) {
			int temp = in.get();
			while (temp >= '0' && temp <= '9') {
				v1.push_back(temp - '0');
				temp = in.get();
			}
			int cont = 0;
			int primi = 0;
			for (divisore = 1; divisore <= 100000; divisore++) {
				if (v1 % divisore == 0)
					cont++;
			}
			out.open("output.txt");
			out << cont;
			out.close();
			in.close();
		}
		return 0;
	}
}

Il fatto è che il codice è inefficiente e in certi casi ci mette troppo tempo.

Sapete come posso fare per risolvere questo problema? Sono due giorni che ci sto su...

[Rggb1]

Urca... mai sentito parlare del crivello di Eratostene?

Stai usando un ciclo con incremento di 1 per calcolare se un numero 'divisore' divide il tuo numero in analisi.
Alternativa: generi 1000 numeri primi e di volta in volta guardi se dividono il numero interessato, ottenendo così i suoi fattori primi (fino a 1000),e te li metti in un array, usando più elementi se il numero primo divide più volte il numero in analisi, es.
2 2 3 3 3 7 13 31 ...
e sulla base di questi generi tutti i divisori.

[apatriarca]

Nota che i divisori primi di $x$ non superano $1000$ allora è abbastanza semplice calcolarti tutti i fattori primi del numero. È infatti sufficiente memorizzare (o calcolare) tutti i numeri primi in questo intervallo e verificare quante volte dividono $x$. Se $x = p_1^{k_1}p_2^{k_2} ... p_n^{k_n}$ allora tutti i divisori sono della forma $p_1^{s_1}p_2^{s_2} ... p_n^{s_n}$ con $s_i < k_i$ per ogni $i \in \{1,2, ... n\}$. In questo modo il problema è ridotto a trovare i divisori primi del numero e calcolare il numero di scritture del tipo $p_1^{s_1}p_2^{s_2} ... p_n^{s_n}$. Inoltre per rappresentare un numero positivo inferiore di $10^18$ puoi usare un intero a 64 bit (long long).

[Umby2]

Il titolo del topic dice "Conteggio dei divisori".

Vorrei capire se ti interessa conoscere quali sono tutti i divisori, oppure sapere quanti sono i divisori di un numero.

P.s. La mia seconda ipotesi la trovo molto interessante.
P.s. Dal programma che hai scritto, capisco che ti interessa solo sapere "quanti"

[Rggb1]

@Umby
Leggendo la traccia dice che vuole sapere quanti sono, non quali sono. Quindi come dicevo è sufficiente calcolare i fattori primi e metterli separatamente in un array per calcolare (contare) tutti i divisori.

Pero' il tuo post è centrato: è evidente che non ci avevo pensato, ma effettivamente non importa nemmeno memorizzare i fattori primi...

[Umby2]

"Rggb":

Quindi come dicevo è sufficiente calcolare i fattori primi e metterli separatamente in un array per calcolare (contare) tutti i divisori.

In che modo, quindi, tu calcoleresti ( conteresti ) il numero di divisori?
Lo chiedo, perchè, ho trovato un "metodo" ed intendevo confrontarlo con il tuo.

[apatriarca]

Essendo evidentemente di un compito, direi che sarebbe meglio non dare, ancora, la soluzione.

[Umby2]

"apatriarca":Essendo evidentemente di un compito, direi che sarebbe meglio non dare, ancora, la soluzione.

Giusto.

Aspettiamo mate, che ritorni.

[ilario991]

"apatriarca":Essendo evidentemente di un compito, direi che sarebbe meglio non dare, ancora, la soluzione.

Non era un compito...

Alla fine ho fatto la scomposizione in fattori primi e ho moltiplicato tra di loro il numero di divisori trovati.