Наскоро ми дадоха задача от университета... да направя програма, която проверява дали дадено число е просто, и ако не е, да му намеря всички делители. Докарах някакъв алгоритъм, който изглежда работи, ама ми се струва, че може да се оптимизира още...
/**************************************************************************
* 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;
}Алгоритъма работи, и е сравнително бърз, но със сигурност има и по-бърз... ако някой има идеи, да споделя
П.С. Пробвах със ситото на Ератостен за намиране на прости числа,.. не е толкова бързо, и изисква много памет.
Покажи участието
