Remove lines 23 and 24 and it will go much faster. You need to use modulus though, not division. If you did use division, you need to check that the result is a whole number.
longlong number = 600851475143;
// now modulus will work
Not to mention doubles have floating point rounding errors, so the odds of you getting an exact whole number as the result of division is extremely slim. (ie: 10.0 / 5.0 might actually give you 1.999999999999 instead of 2.0)
Surely your computer has a calculator which will tell you if 600851475143 is divisible by 71.
I don't know what project 3 is though, took a guess that it has something to do with primes. Is it maybe to find the largest prime number of which the remainder is zero?
Edit: I guess the other reason it doesn't end is because if the number was prime, your loop would never end.
1 2 3 4 5 6 7
else
{
i++;
if (i == number) break; // You didn't find a factor less than number,
// probably don't care about the number itself
goto tryagain; // Obligatory "Don't use gotos, use a for loop"
}
#include <iostream>
#include <cstdint>
#include <cmath>
#include <vector>
int main()
{
// What is the largest prime factor of the number 600851475143 ?
constexpr std::uint64_t N = 600851475143ULL ;
const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ;
// generate a prime number sieve upto the square root of N
std::vector<bool> sieve( SZ, true ) ;
for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] )
for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ;
// check for divisibility from largest prime number downwards
std::size_t i = SZ-1 ;
while( !( sieve[i] && N%i == 0 ) ) --i ;
std::cout << "largest prime factor of " << N << " is " << i << '\n' ;
}
Ya. I pretty much understand what to do now. The only question I have is that Ive tried to use for loops and I always fail with them. How do i do it? I understand them and how to use them but it always ends up badly.
for (int i = 3; modulus(number, i) == 0; ++i)
{
modulus(number, i);
if (modulus(number, i))
{
cout << i;
}
}
The condition is when the remainder is equal to 0. Are functions allowed to be used in the condition? When I run this a blank screen just comes up and then I press enter and exit the program.
If I may dare, I have attempted a translation of JLBorges masterpiece "for the masses" (as the features he used push my envelope as well).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include <iostream>
usingnamespace std;
int main()
{
// What is the largest prime factor of the number 600851475143 ?
unsignedlonglongint N = 600851475143ULL ;
const size_t SZ = 775146;// = floor( sqrt(N) ) as long as we're hardcoding values here
// generate a prime number sieve upto the square root of N
bool sieve[SZ] = {0};
for( size_t i = 2 ; i < SZ ; ++i ) if( !sieve[i] )
for( size_t j = i*i ; j < SZ ; j += i ) sieve[j] = true ;
// check for divisibility from largest prime number downwards
size_t i = SZ-1 ;
while( sieve[i] || N%i ) --i ;
cout << "largest prime factor of " << N << " is " << i << '\n' ;
}
Actually, it's an adaptation. I "reversed" the true/false logic so I could avoid explicitly initializing the sieve array elements to true.
It had an interesting effect upon the logic at line 17, which I assume I got correct because the program still gives the correct answer to Euler #3.
There are some interesting properties of prime numbers that can make solving this problem much faster than testing all numbers. This is a common theme among the Euler problems--to get you to learn something you hadn't realized before. Research prime numbers first, solve the problem second.
@JLBorges. Thank you.
Line 2 is particularly interesting considering several problems I've recently tackled where I'm intermixing type usage explicitly to avoid overflows on products. These include the allocator (MyMalloc/MyFree) problem you saw, and an 8 digit per node link list class for bigInt, which you may or may not have seen (it passed quickly).