problem 3 euler

[approa]

//why is this not working?
// euler problem 3. https://projecteuler.net/problem=3
// there are no syntax errors.
// i am getting no output.

#include <iostream>
#include <cmath>
using namespace std;
bool primeornot(int n)
{
int m = int (sqrt(float(n)));
if (n==2)
return true;

for (int i=2;i<m+1;i=i+1)
{
if (n%i==0)
return false;
}
return true;
}

int main()
{
for (int s= 600851475143 ;s>1;s--)
{
if (600851475143%s==0&&primeornot(s) == true)
{cout<<s;
break;}
}

system("pause");
}

[booradley60]

I'm sure your compiler must have given you a warning. The number 600,851,475,143 is probably too big to fit into an int on your platform. You'll have to use a bigger type; try long long.

[giblit]

Probably because your method is very inefficient and the number is larger than a signed int which would be 2₃₁ - 1 == 2147483647

You are going to need at least a signed long long.

I would highly suggest using a prime sieve for this problem. Or even limiting the primes you are checking since for one the largest possible would be the sqrt which would be 775,000 but even then that is not needed since this number has a fairly small largest factor.


http://www.cplusplus.com/forum/beginner/128706/

[Disch]

ints are typically 32-bit.

int s= 600851475143

This number is way to big to fit inside an int.

In hex, this is 0x8BE589EAC7
When assigned to an integer, it will be truncated to 0xE589EAC7 (high 2 digits are chopped off)

This is a negative number in 2's compliment. Therefore your s > 1 loop condition will immediately fail.

You'll need a solution that does not require such a large variable... or you'll need to use a larger type (like a int64_t from <cstdint>)


The compiler should be generating a warning, telling you that the number is too large for this int. Don't just ignore compiler warnings.


EDIT:

Also, when you cast to a float, you will lose TONS of precision... as a float has even less bits for numerical data than an int does. Consider a larger floating point type (like double, or long double)

EDIT2: holy crap double-ninja'd