0

I have very recently started to learn c, my first coding language. I am trying to solve problem 3 from Project Euler, and I wrote this to do so. This code is meant to identify the largest prime factor of 600851475143, but instead I get a strange return value I don't understand. Anyone know why? 

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i = 1, a = 0, prime = 0;
    for(i = 1; i < 600851475143; i += 2) {
        for(a = 0; a <= i / 2; a++) {
            if(i % a == 0) {
                break;
            }
            if(a = i / 2) {
                if(600851475143 % i == 0) {
                    prime = i;
                }
            }
        }
    }
    printf("%d\n", prime );
    return 0;
}
Luke
  • 9
  • 1
  • 8
    Hint: How many bits does 600851475143 require for storage? – JAB Dec 01 '17 at 01:56
  • 1
    Another problem is `if(a = i / 2)`. This is an assignment to `a`, and will be true as long as `i/2` is non-zero. Presumably you intended it to be `if(a == i / 2)`, which is a comparison. – Tom Karzes Dec 01 '17 at 02:05
  • 3
    Get `-Wall` to compiler option and you'll know most of your mistakes. – iBug Dec 01 '17 at 02:34
  • @JAB `int i; ... i < 600851475143` is a _very_ legitimate concern about the lack of `int i` range, yet OP's code problem first occurs with the attempt to do `i%0`. – chux - Reinstate Monica Dec 01 '17 at 04:50

2 Answers2

3

Division by 0 (or trying to %0). This is undefined behavior (UB) and can explain the return of -1. With UB - anything can happen. The rest of code is not important until this is fixed.

for(a = 0; a <= i / 2; a++) {
  //     v---- a is zero!
  if(i % a == 0) {

Code probably should start as 2.

// for(a = 0; a <= i / 2; a++) {
for(a = 2; a <= i / 2; a++) {

Rather than end at i / 2, end at the √600851475143, it is much sooner.

           v-------------------v Same a <= sqrt(600851475143) without FP or overflow
for(a = 2; a <= 600851475143 / a; a++) {

Other issues exist too. if(a = i / 2) see @Tom Karzes

int likely has a range well within 600851475143, so i < 600851475143 is always true. A common compiler warning will emit this. Be sure to fully enable warnings to save time. @iBug

warning: comparison is always true due to limited range of data type [-Wtype-limits]

Pseudo code solution

int main(void) {
  wide_enough_type n = 600851475143;
  wide_enough_type factor = 1;
  try each i starting at 2 and until  i*i <= n
    repeat as long as n divides into i with no remainder
      make n smaller by diving it by i
      save i as factor
  save the larger of (n, factor) as factor
  printf("Greatest factor: %some_type_specifier\n", factor);
}
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
1

Your problem is called an overflow. All data types have limited range, due to the limited amout of memory available. An int, on an average modern computer, goes usually up to 2,147,483,647 (WARNING: I said usually) - things are in reality a bit more complex. Anyway, your upper limit exceeds this.

What happens when an int (or a signed integer data type) overflows is that, due to some representation related issues, it goes negative. Have a look at two's complement representation for more details about why.

To fix it, use a data type with a broader range. long long goes up to 9,223,372,036,854,775,807, which seems suitable for your needs.

Note that the integer literals need also to be marked as long long, otherwise they will overflow too:

for(i = 1; i < 600851475143LL; i += 2)

If you need integer values larger than the range supported by long long (it doesn't seem to be the case here though), you're out of luck: you need to find some clever way to deal with it.

Something else to look for is that when I ran the code I got a division by 0. I do not know if this is related to the overflow or not.

Paul92
  • 8,827
  • 1
  • 23
  • 37