6 Replies - 290 Views - Last Post: 01 November 2019 - 03:54 PM Rate Topic: -----

#1 Elfkam   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 01-November 19

Need help, cant find solution

Posted 01 November 2019 - 11:16 AM

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

Is This A Good Question/Topic? 0
  • +

Replies To: Need help, cant find solution

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,240
  • Joined: 05-May 12

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.
Was This Post Helpful? 1
  • +
  • -

#3 Elfkam   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 01-November 19

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.

Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,240
  • Joined: 05-May 12

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:
    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?
Was This Post Helpful? 0
  • +
  • -

#5 Elfkam   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 01-November 19

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.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,240
  • Joined: 05-May 12

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.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,240
  • Joined: 05-May 12

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:
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?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1