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

1. 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. > 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.

3. 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. 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. 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"

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

6. 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. 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...)

8. 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. 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