простые множители

Question

Вопрос заключается в том, чтобы написать число п как произведение его простых множителей в 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 секунд

Answer 1

Предупреждение относительно этой линии:

if (prime) return true; 

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

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

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

Answer 2

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

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

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

Answer 3

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

if (prime) 

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

Answer 4

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

Answer 5

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