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

  1. #1
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112

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

    I can't get the program to output just the prime factors (5, 7, 13, and 29) but only all prime numbers of 13195. This is a problem on Project Euler.

    Code:
    /* The prime factors of 13195 are 5, 7, 13 and 29.
    
    
    
    
    /* A prime number is a numeral that is greater than 1 and cannot be divided evenly by any other number except 1 and itself. */
    
    
    #include <stdio.h>
    
    
    int main (void)
    {
    	// long num = 600851475143;
    	// printf("%li\n", num);
    	
    	int num = 13196;
    
    
    	int i, j;
    	int array[13195];
    	int new_array[13195];
    
    
    	for (i = 1; i < num; i++)
    	{
    		// element i of array being passed to second for loop
    		array[i] = i;
    		new_array[i] = i;
    	}
    
    
    	for(i = 1; i < num; i++)
    	{
    		// if array[i] is even, print the value of array[i]
    		if ((13195 % array[i] == 0))  // The prime factors of 13195 are  5, 7, 13, 29
    		{					// 13195 / 29 = whole number
    			new_array[i] = array[i]; // printf("%d, ", array[i]); copied into new_array[i]
    			
    			if((13195 / new_array[i] == 0))  // printf("%d, ",array[i]); 13195 divided by new_array[i] equally is prime factor
    			{
    				printf("%d, ", new_array[i]);
    			}
    			// if 13195 is divided by new_array[i] equally it is a prime factor
    		}
    	}
    
    
    	printf("\n");
    
    
    	return 0;
    }
    Hey all I have a question with this line:

    Code:
    if((13195 / new_array[i] == 0))
    Please what would be the best way to write this division arithmetic inside an if statement, if I replace the divide sign with a modulus operator I get a value to be computed and displayed. Thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,400
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112
    hey & Thanks Salem, i haven't looked at the full solution yet again but this is what i've came up with (program doesn't output any text yet but compiles and runs:

    Code:
    /* prime factorization program */
    /* The prime factors of 13195 are 5, 7, 13, and 29 */
    
    
    #include <stdio.h>
    
    
    
    
    int main (void)
    {
    	int a = 2;
    	int num = 13195;
    	int result[num];
    
    
    	while (a < 13195) 
    	{
    		while ((13195 % a == 0))  // true a is a factor of 13195
    		{
    			if (13195 / a)	  	// if (13195 / a) is is true (returns a whole number) it is a prime factor and print it to the screen. Will always be true because C is treating the result as a whole number.
    			{
    				// printf("%d, ", a); (not prime results)
    				while (a / num)
    				{
    					result[a] = result[a] / num;
    					printf("%d", result[a]);
    					a++;
    				}
    			}
    		}
    		++a;
    	}
    
    
    	printf("\n");
    
    
    	return 0;
    }

  4. #4
    Registered User awsdert's Avatar
    Join Date
    Jan 2015
    Posts
    1,138
    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)

  5. #5
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by awsdert View Post
    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
    Last edited by Hodor; 01-28-2020 at 06:48 PM.

  6. #6
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112
    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;
    }

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by _jamie View Post
    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...)
    Last edited by Hodor; 01-28-2020 at 11:59 PM.

  8. #8
    Registered User
    Join Date
    Feb 2018
    Location
    San Diego, CA
    Posts
    112
    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.

  9. #9
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by _jamie View Post
    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
    Last edited by Hodor; 01-29-2020 at 08:42 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. If statement for array ?
    By Junior Aj Twist in forum C Programming
    Replies: 1
    Last Post: 11-17-2013, 01:39 PM
  2. Replies: 2
    Last Post: 03-20-2012, 08:41 AM
  3. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  4. Divide and Conquer: array in the reverse order
    By Steamer in forum C Programming
    Replies: 11
    Last Post: 03-08-2004, 07:31 PM
  5. array of pfuncs in one statement
    By genghis in forum C++ Programming
    Replies: 4
    Last Post: 01-29-2003, 02:56 PM

Tags for this Thread