Я пытаюсь узнать больше о коде C, пытаясь выполнить примеры на странице Project Eular: http://projecteuler.net/problems В настоящий момент я пытаюсь вычислить наивысший простой множитель числа 600851475143. Вот мой код:
/* The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?*/
#include <stdio.h>
unsigned long long GetPrimeFactor(unsigned long long number)
{
/* printf("The number you typed was %d\n", number);*/
unsigned long long prime = 2;
unsigned long long LargestPrime = 0;
while (prime != 0)
{
if(number%prime == 0)
{
if(number == prime)
{
if(LargestPrime < prime)
LargestPrime = prime;
printf("End of prime factors \nLargest Prime: %d\nEnding Number: %d\n", LargestPrime, number);
break;
}
else if(LargestPrime < prime)
LargestPrime = prime;
//divide number by prime
number = number/prime;
printf("Prime: %d\n", prime);
}
else
{
//get new prime
prime = nextPrimeNumber(prime);
}
}
}
unsigned long long nextPrimeNumber(unsigned long long input)
{
unsigned long long nextPrimeNumber;
while(input !=0)
{
if( input < 0)
{
printf("The number you have entered is negative\n");
}
else if (input > 0)
{
nextPrimeNumber = input + 1;
if(nextPrimeNumber%2 == 0 && nextPrimeNumber != 2)
{
nextPrimeNumber += 1;
}
while(!isPrime(nextPrimeNumber))
{
nextPrimeNumber += 2;
}
return nextPrimeNumber;
}
}
}
int isPrime(int number)
{
int i;
int prime = 1; //true
if(number == 2)
prime = 0; //false
if(number%2 == 0 || number <= 1)
prime = 0;
else
{
for(i=3; i<sqrt(number) && prime == 1; i+=2)
if(number%i == 0)
prime = 0;
}
return prime;
}
int main(void)
{
unsigned long long number;
printf("Enter a Number: \n");
scanf("%d", &number);
GetPrimeFactor(number);
return 0;
}
Этот код работает для числа 13195, которое есть в примере, но не работает, когда я пробую большие числа и не уверен, что не так.
вывод с большим числом 600851475143: простое число: 3 простое число: 29 простое число: 5108231 и т. д. это не может быть правильным, потому что число в любом случае не может делиться на 3.
Не могу понять, что не так, поэтому любая помощь будет отличной
600851475143
необходимо 40 бит для представления в двоичном формате. По-видимому, вашиint
имеют ширину 32 бита. Попробуйте использовать более крупный шрифт, например:long long unsigned
. - person pmg   schedule 16.02.2012int
. Это вызывает проблемы при попытке переключиться на более крупный целочисленный тип. Определите свои функции, прежде чем они будут использоваться. - person Pascal Cuoq   schedule 16.02.2012int isPrime(int number)
должно бытьint isPrime(unsigned long long number)
2) Есть пара мест, где вы проверяете меньше или равно. Убедитесь, что вы не настраиваете себя на провал в этих местах. - person JimR   schedule 16.02.2012