Ответ 1
Факторы парные. 1 и 24, 2 и 12, 3 и 8, 4 и 6.
Улучшение вашего алгоритма может состоять в том, чтобы итерации к квадратному корню из num вместо всего пути к num, а затем вычислить парные коэффициенты с помощью num / i.
Эффективное получение всех делителей заданного числа
В соответствии с этим сообщением мы можем получить все делители числа через следующие коды.
for (int i = 1; i <= num; ++i){
if (num % i == 0)
cout << i << endl;
}
Например, делителями числа 24 являются 1 2 3 4 6 8 12 24.
После поиска некоторых связанных сообщений я не нашел хороших решений. Есть ли эффективный способ сделать это?
Мое решение:
- Найти все простые коэффициенты заданного числа через это решение.
- Получить все возможные комбинации этих простых факторов.
Однако, похоже, это нехорошо.
Ответы
Ответ 2
Вы должны действительно проверить до квадратного корня из числа, как sqrt (num) * sqrt (num) = num:
Что-то в этих строках:
int square_root = (int) sqrt(num) + 1;
for (int i = 1; i < square_root; i++) {
if (num % i == 0&&i*i!=num)
cout << i << num/i << endl;
if (num % i == 0&&i*i==num)
cout << i << '\n';
}
Ответ 3
В настоящее время нет эффективного способа в смысле алгоритмической сложности (алгоритма с полиномиальной сложностью), известного в науке. Таким образом, повторение до тех пор, пока квадратный корень, как уже было предложено, в основном так же хорош, как и вы.
В основном из-за этого большая часть используемой криптографии в настоящее время основана на предположении, что для вычисления простой факторизации любого заданного целого требуется очень много времени.
Ответ 4
Здесь мой код:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define pii pair<int, int>
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032
unsigned base[MAX / 64], segment[RNG / 64], primes[LEN];
#define sq(x) ((x)*(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))
// http://zobayer.blogspot.com/2009/09/segmented-sieve.html
void sieve()
{
unsigned i, j, k;
for (i = 3; i<LMT; i += 2)
if (!chkC(base, i))
for (j = i*i, k = i << 1; j<MAX; j += k)
setC(base, j);
primes[0] = 2;
for (i = 3, j = 1; i<MAX; i += 2)
if (!chkC(base, i))
primes[j++] = i;
}
//http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
vector <pii> factors;
void primeFactors(int num)
{
int expo = 0;
for (int i = 0; primes[i] <= sqrt(num); i++)
{
expo = 0;
int prime = primes[i];
while (num % prime == 0){
expo++;
num = num / prime;
}
if (expo>0)
factors.push_back(make_pair(prime, expo));
}
if ( num >= 2)
factors.push_back(make_pair(num, 1));
}
vector <int> divisors;
void setDivisors(int n, int i) {
int j, x, k;
for (j = i; j<factors.size(); j++) {
x = factors[j].first * n;
for (k = 0; k<factors[j].second; k++) {
divisors.push_back(x);
setDivisors(x, j + 1);
x *= factors[j].first;
}
}
}
int main() {
sieve();
int n, x, i;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
primeFactors(x);
setDivisors(1, 0);
divisors.push_back(1);
sort(divisors.begin(), divisors.end());
cout << divisors.size() << "\n";
for (int j = 0; j < divisors.size(); j++) {
cout << divisors[j] << " ";
}
cout << "\n";
divisors.clear();
factors.clear();
}
}
Первая часть, sieve() используется для нахождения простых чисел и помещает их в массив primes []. Перейдите по ссылке, чтобы узнать больше об этом коде (побитное сито).
Вторая часть primeFactors (x) принимает целое число (x) в качестве входных данных и обнаруживает ее простые множители и соответствующий показатель и помещает их в векторные факторы []. Например, primeFactors (12) будут заполнять факторы [] следующим образом:
factors[0].first=2, factors[0].second=2
factors[1].first=3, factors[1].second=1
как 12 = 2 ^ 2 * 3 ^ 1
Третья часть setDivisors() рекурсивно вызывает себя для вычисления всех делителей x с использованием векторных факторов [] и помещает их в векторные делители [].
Он может вычислять дивизоры любого числа, которое вписывается в int. И это довольно быстро.
Ответ 5
Существует множество хороших решений для нахождения всех основных факторов не слишком большого числа. Я просто хотел отметить, что, как только они у вас есть, не требуется никаких вычислений, чтобы получить все факторы.
если N = p_1^{a}*p_{2}^{b}*p_{3}^{c}.....
Тогда число факторов ясно (a+1)(b+1)(c+1).... так как каждый фактор может встречаться от нуля до одного раза.
например, 12 = 2^2*3^1 поэтому он имеет 3*2 = 6 факторов. 1,2,3,4,6,12
======
Первоначально я думал, что вы просто хотели количество различных факторов. Но та же логика применима. Вы просто перебираете набор чисел, соответствующих возможным комбинациям показателей.
Итак, в приведенном выше примере:
00
01
10
11
20
21
дает вам 6 факторов.
Ответ 6
//Try this,it can find divisors of verrrrrrrrrry big numbers (pretty efficiently :-))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<conio.h>
using namespace std;
vector<double> D;
void divs(double N);
double mod(double &n1, double &n2);
void push(double N);
void show();
int main()
{
double N;
cout << "\n Enter number: "; cin >> N;
divs(N); // find and push divisors to D
cout << "\n Divisors of "<<N<<": "; show(); // show contents of D (all divisors of N)
_getch(); // used visual studio, if it isn't supported replace it by "getch();"
return(0);
}
void divs(double N)
{
for (double i = 1; i <= sqrt(N); ++i)
{
if (!mod(N, i)) { push(i); if(i*i!=N) push(N / i); }
}
}
double mod(double &n1, double &n2)
{
return(((n1/n2)-floor(n1/n2))*n2);
}
void push(double N)
{
double s = 1, e = D.size(), m = floor((s + e) / 2);
while (s <= e)
{
if (N==D[m-1]) { return; }
else if (N > D[m-1]) { s = m + 1; }
else { e = m - 1; }
m = floor((s + e) / 2);
}
D.insert(D.begin() + m, N);
}
void show()
{
for (double i = 0; i < D.size(); ++i) cout << D[i] << " ";
}
Ответ 7
int result_num;
bool flag;
cout << "Number Divisors\n";
for (int number = 1; number <= 35; number++)
{
flag = false;
cout << setw(3) << number << setw(14);
for (int i = 1; i <= number; i++)
{
result_num = number % i;
if (result_num == 0 && flag == true)
{
cout << "," << i;
}
if (result_num == 0 && flag == false)
{
cout << i;
}
flag = true;
}
cout << endl;
}
cout << "Press enter to continue.....";
cin.ignore();
return 0;
}
Ответ 8
Вот Java-реализация этого подхода:
public static int countAllFactors(int num)
{
TreeSet<Integer> tree_set = new TreeSet<Integer>();
for (int i = 1; i * i <= num; i+=1)
{
if (num % i == 0)
{
tree_set.add(i);
tree_set.add(num / i);
}
}
System.out.print(tree_set);
return tree_set.size();
}
Ответ 9
for (int i = 1; i*i <= num; ++i)
{
if (num % i == 0)
cout << i << endl;
if (num/i!=i)
cout << num/i << endl;
}
Ответ 10
//DIVISORS IN TIME COMPLEXITY sqrt(n)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll int n;
cin >> n;
for(ll i = 2; i <= sqrt(n); i++)
{
if (n%i==0)
{
if (n/i!=i)
cout << i << endl << n/i<< endl;
else
cout << i << endl;
}
}
}
Ответ 11
мы также можем ссылаться на использование простых факторов в числе Например::
100
/ \
10 10
/ \ / \
2 5 5 2
таким образом, имеем (2 ^ 2) (5 ^ 2) отсюда мы добавим 1 к степеням 2 и 5. Теперь мы имеем 3 * 3 = 9 как общее число факторов 100 (а именно 1, 2,4,5,10,20,25,50,100) Таким образом, мы можем использовать этот подход для поиска коэффициентов очень больших чисел и в конечном итоге сокращения количества итераций.
Ответ 12
Я сделал один с более простыми понятиями, но все еще работает нормально
enter code here
#include <iostream>
#include <stdio.h>
#include <math.h>
bool loop = true;
int x,y,z=1;
using namespace std;
void menu(){
cout << "\n Inserisci il numero da anaizzare : "; #it insetrs the number
that will be analised
cin >> x;
}
void algoritmo(){
for (int y=1;y<=x;y++){
if (x%y!=0){
y++;
}
else{
cout << " " << y;
}
}
}
int main(){
while (loop == true){
menu(); #this is the void for the menu
algoritmo(); #this is the void the algorithm
}
return 0;
}
Ответ 13
for( int i = 1; i * i <= num; i++ )
{
/* upto sqrt is because every divisor after sqrt
is also found when the number is divided by i.
EXAMPLE like if number is 90 when it is divided by 5
then you can also see that 90/5 = 18
where 18 also divides the number.
But when number is a perfect square
then num / i == i therefore only i is the factor
*/