Как разложить число на множители(си)?

Question

[quarttt]

Заполните тело функции, которая принимает число n​​ и с помощью указателей заполняет два числа множителями a​​ и b​​ такими, что:

Если n=1 или n простое, то a = 1, b = n.
Если n составное, то мы ищем ab=n​​ такие, что 1< a<= b
a - наименьший множитель.
Гарантируется, что n>0​​.

void factorize( int n, int* a, int* b )
{
...
}

Не получается остановиться только на двух множителях. Помогите, пожалуйста, написать функцию
Примерно понял как посчитать, но с написанием программы туговато. Вот что придумал:
•Половина чисел - чётные;
•Если число нечётное, то проверять есть смысл только нечётные числа.
•Делители числа не превышают его половины. А вообще даже квадратного корня из него

Answer 1

[ZIK1337]

Используйте алгоритм Ферма

Answer 2

[Wataru]

Не получается остановиться только на двух множителях.

Приведите ваш код, который не останавливается. По идее, достаточно в него вставить return после нахождения первой пары множителей.

Comments

[quarttt]

void factorize( int n, int* a, int* b )
{
    for (int i = 2; i * i <= n; i++) {
        if ((n % i)==0) {
            *a=i;
            *b=n/i;
            return;  
        } else {
          *a=1;
          *b=n;
        }
    }
    if (n==1) {
      *a=1;
      *b=n;
    }    
}

Вроде все работает, но хотелось бы как-то уменьшить время. Пишу с телефона, поэтому структура корявая)))

[Wataru]

quarttt, никак особо не уменьшить, быстрее чем за корень простого решения нет (есть очень тяжелые математические методы через эллиптические кривые, но там степень не сильно меньше 0.5. Можно else вывести за цикл. Если из цикла не вернулось, то можно всегда присваивать 1, n. Будет чуть быстрее.