Thread: divide array and value & array value in if() statement

> int array[13195];
> int new_array[13195];
This approach is totally impractical for any large number.

Write a loop which just gives you the next prime number to begin with, then progress to potential divisors.

Originally Posted by awsdert

Dude, this would be the correct way to calculate prime numbers:

Code:

#include <stdio.h>
int main() {
    unsigned i, j, cap = 13196;
    char *is = " is Prime\n", *not = " is not Prime\n";
    printf("0%s1%s2%s", not, not, is );
    for ( i = 3; i < cap; ++i ) {
        for ( j = 2; j < i; ++j ) {
            if ( i % j == 0 ) break;
        }
        printf( "%d%s", i, ((j == i) ? is : not) );
    }
    return 0;
}

Just store the boolean values in an allocated array because stack functions don't always get given that much space to work with (even if 9 times out of 10 they do)

Actually you don't need to test for primeness at all for this problem. I think what the OP is trying to do is this:

Code:

Given a number "num"
Start with factor = 2

while num > 1
    if num % factor == 0 then   ;; factor is a factor (not necessarily prime) of num 
        num = num / factor     ;; divide out the factor from num
    else
        factor = factor + 1 ;; next candidate factor (doesn't matter if it's prime or not)
    end if
end while
;; factor is now the largest prime factor

Edit:

Code:

Starting with num: 13195 and factor: 2
num:  13195 factor: 5
Dividing out the factor 5... num / 5 = 2639
num:   2639 factor: 7
Dividing out the factor 7... num / 7 = 377
num:    377 factor: 13
Dividing out the factor 13... num / 13 = 29
num:     29 factor: 29
Dividing out the factor 29... num / 29 = 1
Largest prime factor: 29

Of course you could store all the primes <= sqrt(num) in an array and do it that way. Just doesn't seem necessary because even if a given factor is not prime dividing out the factor from num eliminates that factor anyway

Originally Posted by _jamie

this is what I've came up so far, next step for me is work on adding the code for the largest prime factor instead of all 4 of them being printed out. Thanks to all on the forum for the continuous help. FYI the numbers in the new code i am posting is a 12 digit long number which is part of the actual question instead of a 5 digit int on my first post. Problem 3 - Project Euler

Code:

/* What is the largest prime factor of the number 600851475143 ? */
// 6857


#include <stdio.h>


int main (void)
{
    long num = 600851475143;
    long a = 2;


    // while (a < num)
    while (num != 1)
    {
        if (num % a == 0)
        {
            while (num % a == 0)
            {
                num = num / a;
                printf("%ld, ", a);
            }


        }
        a++;
    }
    
    printf("\n");
    
    return 0;
}

Well, you've already done it. Remove line 22 (the printf in the loop) and change line 30 to simply print the value of a

Edit:

Code:

$ factor 600851475143
600851475143: 71 839 1471 6857

You're eliminating factors in ascending order so the value of 'a' when the while loop finishes is the largest factor. If you want to be paranoid I guess you could write an isPrime function and check that 6857 is truly prime (but it must be because you've already eliminate any prime or composite factors less than 6857, so 6857 must be prime) (and the command line factor program prints prime factors only, so if you're getting 6857 then...)

Originally Posted by _jamie

euler_3.c
Hey Hodor just a quick comment I got a different answer and added a "-1" to my printf statment, I saw the ++ operator and was wondering if this was correct syntax to get the right answer. Also I was looking at your pseudocode paragraph under your "I think what the OP is trying to do is this"... and i've started a word document following this for my next programming problem #4 on Project Euler and I will be posting i'm sure, thanks. I attached my source file as an attachment because I can't get it to open at this public computer without a proper text editor.

Ok, I missed that. The only difference (apart from the inner while loop that you've used, which is fine) from the pseudocode I wrote is that you're always incrementing 'a' whereas the pseudocode only increments 'a' when a is not a factor. the ++ operator is correct. You could leave your code as-is, subtracting 1, or you could add an else

Your code (my changes in bold):

Code:

/* What is the largest prime factor of the number 600851475143 ? */
// 6857

#include <stdio.h>

int main (void)
{
    long num = 600851475143;
    long a = 2;

    printf("%ld: ", num);
    // while (a < num)
    while (num != 1)
    {
        if (num % a == 0)
        {
            while (num % a == 0)
            {
                num = num / a;
                // printf("%ld\n", a);
            }
        } else {
            ++a;
        }
    }
    
    printf("Max prime factor %ld", a);
    printf("\n");
    
    return 0;
}

I don't think it makes much of a difference as long as you know that in your original version 'a' will be one too high and therefore you need to subtract 1, which you did. Your inner while, though, might be better written as a do-while