Алгоритъм за изчисляване на делителите на число

[Vexorian]

Наскоро ми дадоха задача от университета... да направя програма, която проверява дали дадено число е просто, и ако не е, да му намеря всички делители. Докарах някакъв алгоритъм, който изглежда работи, ама ми се струва, че може да се оптимизира още...

Код: [Маркирай кода]


/**************************************************************************
 * Problem number - 4.2
 *  Problem description - check if a number is prime, and if not, find it's
 * divisors
 * Author: Viktorio El Hakim
 **************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>

typedef unsigned long ulong;


/**************************************************************************
 *  Function bIsPrime
 * Description:
 * Checks if an unsigned long is ulPrimes
 *  Arguments: n - the unsigned long to be checked
 **************************************************************************/
bool bIsPrime(ulong ulNum) {
  ulong i = 2;
  if (ulNum < 2)
    return false;
  else if(ulNum == 2)
    return true;
  for(i = 2;i <= sqrt((double)ulNum);i++)
    if (ulNum % i == 0)
      return false;
  return true;
}
/**************************************************************************
 *  Function Divisors
 * Description:
 * Prints all the ulDivisors of a number
 *  Arguments: ulNum - the number to be factorized
 **************************************************************************/
void Divisors(ulong ulNum)
{
ulong i, k, ulTmp = ulNum, ulPrime[100], ulPower[100], ulPCtr = 0, * ulPrimes, * ulDivisors, ulTotal = 0;

printf("1 ");
for(i = 2;i < (ulong)-1 && ulTmp != 1;i++) //First factorize by ulPrimes
{
if(bIsPrime(i) && !(ulTmp % i))
{
ulPower[ulPCtr] = 0;
ulPrime[ulPCtr] = i;
while(!(ulTmp % i))
{
ulTmp /= i;
ulPower[ulPCtr]++;
ulTotal++;
}
ulPCtr++;
}
else if(bIsPrime(ulTmp))
{
ulPrime[ulPCtr] = ulTmp;
ulPower[ulPCtr] = 1;
ulTmp /= ulTmp;
ulTotal++;
ulPCtr++;
}
}
ulPrimes = (ulong*)malloc(ulTotal*sizeof(ulong)); //Allocate memory for the ulPrimes and divisors
ulDivisors = (ulong*)malloc(ulTotal*ulTotal*sizeof(ulong));
ulTotal = 0;
for(i = 0;i < ulPCtr;i++) //Copy all the primes, into the array
{
while(ulPower[i]--)
{
ulPrimes[ulTotal] = ulPrime[i];
ulDivisors[ulTotal] = 0;
ulTotal++;
}
}

for(i = 0;i < ulTotal;i++) //Calculate all the divisors
{
ulong ulAccumulator = 1;
for(k = 0;k < ulTotal;k++)
{
ulAccumulator *= ulPrimes[k];
ulDivisors[i*ulTotal+k] = ulAccumulator;
}
for(k = 0;k < ulTotal-1;k++)
ulPrimes[k] ^= ulPrimes[k+1] ^= ulPrimes[k] ^= ulPrimes[k+1];
}

for(i = 0;i < ulTotal*ulTotal;i++) //Print the divisors
{
bool bInTable = false;
for(ulPCtr = 0;ulPCtr < i && !bInTable;ulPCtr++)
bInTable = ulDivisors[i] == ulDivisors[ulPCtr];
if(!bInTable)
printf("%u ", ulDivisors[i]);
}
printf("\n");
free((void*)ulDivisors);
free((void*)ulPrimes);
}
/**************************************************************************
 *  Function main
 * Description:
 * Main entry for the program
 **************************************************************************/
int main()
{
char chAgain;
printf("This program will determine if a number is ulPrimes, and if it's not, the dividers will be printed.\n");
do
{
ulong ulNumber;

printf("Enter the number you wish to check: ");
scanf("%ul",&ulNumber);

if(bIsPrime(ulNumber))
printf("The number is prime!\n");
else
{
printf("The number is not prime, it's divisors are: ");
if(ulNumber)
Divisors(ulNumber);
else
printf("Every number\n");
}
printf("Would you like to check again? (y/n)\n");
chAgain = getch();
}while(chAgain == 'y');
return 0;
}

Алгоритъма работи, и е сравнително бърз, но със сигурност има и по-бърз... ако някой има идеи, да споделя  

П.С. Пробвах със ситото на Ератостен за намиране на прости числа,.. не е толкова бързо, и изисква много памет.

[Vexorian]

Алгоритъма е само за полижителни... и алгоритъма не е за "сортиране" на числата, а просто извеждане... сега ако може по-конструктивни идеи, относно алгоритъма, не как биват извеждани данните....

[sv_shady]

Ами Ератостен върши работа само ако трябва да намериш повече прости числа. Например, ако пишеш нещо с криптиране и позлваш за ключове прости числа, Ератостен ще е по бързо, от колкото ако итеративно проверяваш всяко число дали е просто или не
Такам иначе май си се задълбал в проблема и не си го погледнал от друга страна Какво означава едно число да е просто? Означава делителите му да са 1 и самото него. За това напълно достатъчно ти е да тръгнеш с един цикъл от 1 до корен квадратен от числото n. Ако намериш делител d в този интервал то съществува и делител n/d. И накрая проверяваш броя делители, ако са 2 значи е просто. Ако са повече от два ги извеждаш Общо взето е почите като твоето, но си разделил проблема изкуствено на две части. Ако се съмняваш ще го напиша моето и ще тестваме за скорост

Едит:
Сега като се загледах по-подробно в кода изниква следния въпрос:
За всички делители си говорим или за всички прости делители защото са две различни неща.

[Vexorian]

За всички делители

@Raev: щом толкова те притеснява ще го оправя, не е кой знае колко.. един "if" хаха

[sv_shady]

Стига сте се заяждали за глупости Ами щом си говорим за всички делители пробвай да напишеш нещо по коментара и идеята ми Тогава обаче защо проверяваш дали числото, за което ще проверяваш дали е делител, е просто

[Vexorian]

Алгоритъма е чист експеримент. Идеята ми беше да раздробя числото на прости делители, и спрямо тези делители да намеря останалите, които всъщтност са комбинации от простите делители. Има един недостатък.. алгоритъма намира и повтарящи се делители... Иначе, програмата е написана малко "тъпо" ама гледам да се съобразявам с материала. Е примерно не би трябвало да използвам "malloc".

П.С. Пробвах с твоя алгоритъм:

Код: [Маркирай кода]

void Divisors(ulong ulNum)
{
        printf("1 ");
for(ulong k = 2;k <= sqrt((double)ulNum);k++)
{
if(ulNum % k == 0) printf("%u ",k);
}
printf("%u\n",  ulNum);
}
Определено е бърз. Не мога да преценя дали е по-бърз от моя.. пробвах с 4294967295, не изкарва всички делители