Основные факторы

Question

Основные факторы

Вопрос состоит в том, чтобы написать число n как произведение его главных факторов в C ++

Например 14 = 2 * 7

24 = 2 * 2 * 2 * 3

5 = 5.

Мой код:

#include <iostream>
#include <cmath>
using namespace std;
bool prime(int n)
{
for (int i=2;i<=sqrt(n);i++)
{
if (n%i==0) return false;
}
if (prime) return true;
}

int main ()
{
int n;
int k=0,a[10000]={0};
cin>>n;
while (n!=1)
{
for (int i=2;;)
{
if (n%i==0 && prime(i)) {n/=i; a[k]=i;k++; }
else i++;
if (n==1) break;
}
}
cout<<a[0];
int s=1;
while (a[s]!=0)
{
for (s=1;;s++)
{
if (a[s]==0) break;
cout<<"*"<<a[s];
}
}
return 0;
}

Но проблема в ограничении времени, и compiler_stderr.txt показывает мне это сообщение:

solver.cpp: In function `bool prime(int)':
solver.cpp:11: warning: the address of `bool prime(int)', will always evaluate as `true'

И когда я ввожу 2147483647, он снова показывает мне этот номер, но через 5 или 6 секунд.

-1

c++prime-factoring

Решение

Другие решения

Я не думаю, что вы должны проверять, если prime определяется до вашего возвращения true.

Попробуйте следующее

bool prime(int n)
{
for (int i=2;i<=sqrt(n);i++)
{
if (n%i==0) return false;
}
return true;
}

0

Прочитайте предупреждение. Помните, что у компилятора есть причина, а не для предупреждения. Как только вы это сделаете, вашу ошибку легко найти:

if (prime)

простое это имя функции. Во многих ситуациях имя функции автоматически преобразуется в адрес функции. В операторе if проверяющее выражение проверяется на ноль или не ноль. Адрес функции prime никогда не является нулевым указателем, поэтому выражение «if» всегда будет иметь значение true.

0

Нет необходимости в простой функции с текущим кодом. Простая повторная проверка (n% i) == 0 устранит все степени простых чисел, поскольку будет продолжать добавлять i в k [] до тех пор, пока не будет больше факторов i. Если предположить, что 4 является фактором n, то когда я достигну 4, он не будет фактором, потому что он уже был разделен с n / = i, когда мне было 2, (k [0] = 2, k [1] = 2). k [] будет в конечном итоге с простыми множителями n без необходимости в простой функции.

0

Поскольку адрес prime является никогда не ноль, это всегда вернется true, Так что программа будет работать отлично. Хотя, возможно, вы захотите написать это более читабельно: return true; и удалите проверку состояния.
2147483647 это очень большое число, и ваша программа выполняется за O (n ^ 1.5) времени. Таким образом, вы можете предположить, что он работает в порядке 2147483647^1.5 раз. Отсюда и задержка на выходе. Вы можете попытаться уменьшить сложность, используя другой метод, такой как этот.

0

Источник

Accepted Answer

Предупреждение относится к этой строке:

if (prime) return true;

Это не вызывает функцию, она просто проверяет значение указателя функции. Поскольку это не нулевой указатель, это всегда правда.

Если вы достигнете этой точки в функции, ни один из тестов для делителей не пройден, поэтому вы должны просто вернуть true без тестирования ничего.

Причина, по которой ваша программа так долго возвращает ответ, заключается в том, что вы используете неэффективный метод для проверки простых чисел. Вы должны только проверять другие простые числа, используя Сито Эратосфена. Также вам следует позвонить sqrt(n) только один раз, перед циклом, и сохраните его значение в переменной; Вычисление квадратного корня стоит дорого, поэтому вы не хотите делать это каждый раз.

2