Форум по Роботика
Технически форум => Програмиране => Темата е започната от: Vexorian в Октомври 08, 2009, 11:11:40 pm
-
Наскоро ми дадоха задача от университета... да направя програма, която проверява дали дадено число е просто, и ако не е, да му намеря всички делители. Докарах някакъв алгоритъм, който изглежда работи, ама ми се струва, че може да се оптимизира още...
/**************************************************************************
* 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;
}
Алгоритъма работи, и е сравнително бърз, но със сигурност има и по-бърз... ако някой има идеи, да споделя :D
П.С. Пробвах със ситото на Ератостен за намиране на прости числа,.. не е толкова бързо, и изисква много памет.
-
Алгоритъма е само за полижителни... и алгоритъма не е за "сортиране" на числата, а просто извеждане... сега ако може по-конструктивни идеи, относно алгоритъма, не как биват извеждани данните....
-
Ами Ератостен върши работа само ако трябва да намериш повече прости числа. Например, ако пишеш нещо с криптиране и позлваш за ключове прости числа, Ератостен ще е по бързо, от колкото ако итеративно проверяваш всяко число дали е просто или не :)
Такам иначе май си се задълбал в проблема и не си го погледнал от друга страна :) Какво означава едно число да е просто? Означава делителите му да са 1 и самото него. За това напълно достатъчно ти е да тръгнеш с един цикъл от 1 до корен квадратен от числото n. Ако намериш делител d в този интервал то съществува и делител n/d. И накрая проверяваш броя делители, ако са 2 значи е просто. Ако са повече от два ги извеждаш :) Общо взето е почите като твоето, но си разделил проблема изкуствено на две части. Ако се съмняваш ще го напиша моето и ще тестваме за скорост :)
Едит:
Сега като се загледах по-подробно в кода изниква следния въпрос:
За всички делители си говорим или за всички прости делители защото са две различни неща.
-
За всички делители :)
@Raev: щом толкова те притеснява ще го оправя, не е кой знае колко.. един "if" хаха
-
Стига сте се заяждали за глупости :) Ами щом си говорим за всички делители пробвай да напишеш нещо по коментара и идеята ми :) Тогава обаче защо проверяваш дали числото, за което ще проверяваш дали е делител, е просто ???
-
Алгоритъма е чист експеримент. Идеята ми беше да раздробя числото на прости делители, и спрямо тези делители да намеря останалите, които всъщтност са комбинации от простите делители. Има един недостатък.. алгоритъма намира и повтарящи се делители... Иначе, програмата е написана малко "тъпо" ама гледам да се съобразявам с материала. Е примерно не би трябвало да използвам "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, не изкарва всички делители