finding biggest prime factor
Check out the following question:
-------------------------------------------------------
Prime factors of 40 are 2,5.
Find the biggest prime factor of 600851475143.
-------------------------------------------------------------------
I wrote the following code in C but it does not work. Please share your ideas.
/* Program To calculate largest prime factor of 600851475143
* working simultaneously with long and double types is hard. this number
* doesn't fit in a long type variable. so we have to take another measure.
* maybe creating prime numbers and storing them in an array will be better.
*/
#include<stdio.h>
#include<math.h>
int IsPrime(unsigned long num)
{
int index;
int count=0; /* num itself and number One is not counted, so count==0 after loop determines answer*/
/* index from num/2 because a numbers factors are not bigger than its half*/
for(index=sqrt(num);index>1;index--)
if(num%index==0) count++;
return count==0?1:0;
}
int main()
{
const double LargeNum=600851475143;
int largestPrimeFactor;
unsigned long i;
printf("LargeNum: %f",LargeNum);
/* double sqrtLargeNum=sqrt(LargeNum);
printf("sqrt: %f\n",sqrtLargeNum);
*/
printf("long i: %u",i);
for(i=LargeNum/2;i>1;i--)
// if(LargeNum%i==0) /* Is i a factor? */
if(IsPrime(i)){ /* Is i a prime? */
largestPrimeFactor=i;
break;
}
printf("Largest Prime Factor: %d\n",largestPrimeFactor);
return 0;
}
- ۹۲/۰۲/۰۶