Hello, i would like to ask you for help.

I did program which decomposing numbers into prime numbers. Everything works but if i have input for example 500 random numbers its slower then it should.

In one part of my task i get a lot of primes (500) and my program doesnt check it in time.

Any suggestions how to make it faster? ( it has to work for other inputs like number 991350783547)

thanks for help.

Code : https://github.com/E...b/master/Primes

# Need help, cant find solution

Page 1 of 1## 6 Replies - 316 Views - Last Post: 01 November 2019 - 03:54 PM

##
**Replies To:** Need help, cant find solution

### #2

## Re: Need help, cant find solution

Posted 01 November 2019 - 11:36 AM

Please do not post your code on an external site. Please post it here so that most users will have a chance to view it on, as well as help maintain the context of the conversation.

Even though there is a high probability that GitHub will be less ephemeral than other code pasting locations, recall that git allows you to rewrite history. So the code that you share now, and someone comments on today maybe different in the future, and the comment made here will looks out of context.

Even though there is a high probability that GitHub will be less ephemeral than other code pasting locations, recall that git allows you to rewrite history. So the code that you share now, and someone comments on today maybe different in the future, and the comment made here will looks out of context.

### #3

## Re: Need help, cant find solution

Posted 01 November 2019 - 11:52 AM

ok sorry here is my code:

#include <stdio.h> #include <math.h> #define max 1000000 void decomposition(long long a, int array_primes[], int positions){ // function for decomposing numbers into prime numbers int exponent =0; if (a==1){ printf("%lld", a); } while (a != 1){ for (int i=0; i < positions; i++){ while (a % array_primes[i] == 0){ a = a / array_primes[i]; exponent +=1; } if (exponent > 1){ printf("%d^%d", array_primes[i], exponent); if (a != 1 ){ printf(" x "); } } if (exponent == 1){ printf("%d", array_primes[i]); if (a != 1 ){ printf(" x "); } } exponent =0; } } } int main(void){ long long z=0; int array_nums[max]; int b; for (int i=2; i < max; i++){ // part of Eratosthen sieve - array of numbers array_nums[i] = i; } for (int i=2; i < max; i++){ // part of Eratosthen sieve - array with primes and with 0 if (array_nums[i] != 0){ b = 2*i; for (int j = b; j < max; j=j+i){ array_nums[j] = 0; } } } int array_primes[max]; int positions = 0; for(int i=2; i < max; i++){ // part of Eratosthen sieve - copy to another array but without 0 if (array_nums[i] != 0){ array_primes[positions] = array_nums[i]; positions++; } } for (int i=1; i > 0; i++){ if ((scanf("%lld", &z) !=1) || z < 0){ fprintf(stderr, "Error: Wrong input!\n"); return 100; } if (z==0) { return 0; } printf ("Primitive number decomposition %lld is:\n", z); decomposition(z, array_primes, positions); printf("\n"); } }

This post has been edited by **Skydiver**: 01 November 2019 - 11:57 AM

Reason for edit:: Put code in code tags. Learn to do this yourself.

### #4

## Re: Need help, cant find solution

Posted 01 November 2019 - 11:56 AM

Anyway, one of the first steps to save time is make sure that your sieve works correctly and efficiently.

Check your resulting primes from this first:

Check your code above against how the sieve of Erastothenes is supposed to work. Try your code with pen and paper or on a whiteboard. What do you observe?

Check your resulting primes from this first:

for (int i=2; i < max; i++){ // part of Eratosthen sieve - array of numbers array_nums[i] = i; } for (int i=2; i < max; i++){ // part of Eratosthen sieve - array with primes and with 0 if (array_nums[i] != 0){ b = 2*i; for (int j = b; j < max; j=j+i){ array_nums[j] = 0; } } }

Check your code above against how the sieve of Erastothenes is supposed to work. Try your code with pen and paper or on a whiteboard. What do you observe?

### #5

## Re: Need help, cant find solution

Posted 01 November 2019 - 02:51 PM

I am little confused, i think its work correctly. On line 4 for cycle storing 0 instead 2, 4, 6 etc. After that its for number 3, 6, 9 etc.

### #6

## Re: Need help, cant find solution

Posted 01 November 2019 - 03:48 PM

Sorry my mistake. I'm the one who had to look closer. Bad font settings on my phone. I was reading j=j+i as j=j+1.

### #7

## Re: Need help, cant find solution

Posted 01 November 2019 - 03:54 PM

To speed things up, you need to change the condition for your for loop on line 10:

Here's some leading questions:

Can you ever have a factor that is bigger than the number you are trying to decompose?

Why do you have line 9?

for (int i=0; i < positions; i++)

Here's some leading questions:

Can you ever have a factor that is bigger than the number you are trying to decompose?

Why do you have line 9?

Page 1 of 1