C++ program running too slow

wulk18 · Jun 28, 2013

I am new to c++ and started learning last month.I am trying to solve this problem:-

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I wrote this program to take any number from user and return the smallest positive number that is evenly divisible by all of the numbers from 1 to that number.

The problem is the program is taking a lot of time to return the answer. Why?

The prime number function in this prog returns the nth prime number eg. if you pass the value 1, you get 2 as it the first prime number. If you pass 3, you get the third prime number ie 5. And the function smallest returns the answer to the whole problem of smallest positive numbers.

The whole problem seems that the primenumber function is too slow.When I wrote a program to print the first 100 prime number, it did display the first 9 - 10 primenumbers instantly, but for the next numbers were displayed after a gap of few seconds and and the gap got longer and longer as more prime numbers were displayed. I am with i3 and 4gb ram and dont expect this from a 40 line code.

What is the reason? How can I make my code more efficient?

The program:-

#include <iostream>
using namespace std;

int nAnswer = 1;

int primenumber(int x)
{
if(x==1)
return 2;

int iii = (primenumber(x-1)) + 1;

for(int n = (x-1);n >= 1;n--)
{
int z;
z = iii%(primenumber(x-n));
if(z==0)
{iii++;
n=x;}

}

return iii;
}

int smallest(int f)
{

for(int n=1;(primenumber(n))<=f;n++)
{nAnswer = nAnswer * (primenumber(n));}

for(int iii=2;int jjj=1;(primenumber(jjj)^iii)<=f)
{nAnswer = nAnswer * ((primenumber(jjj))^iii);
if (((primenumber(jjj))^(iii+1))<=f)
{iii++;
continue;}
else if(((primenumber(jjj+1))^2)<=f)
{iii=2;
jjj++;
continue;}
else
{break;}}

return nAnswer;}

int main()

{
int g;
cin>>g;
cout << smallest(g); //calling the function
return 0;

}

skeletor · Jun 28, 2013

Just brute force it.

PHP:

#include <stdio.h>

int main()
	{
	int i=20;
	while (i%2!=0 || i%3!=0 || i%4!=0 || i%5!=0 || i%6!=0 || i%7!=0 || i%8!=0 || i%9!=0 || i%10!=0 || i%11!=0 || i%12!=0 || i%13!=0 || i%14!=0 || i%15!=0 || i%16!=0 || i%17!=0 || i%18!=0 || i%19!= 0 || i%20!=0)
		{
		i+=20;
		}
	printf("Number = %d\n",i);
	return 0;
	}

Cool Joe · Jun 29, 2013

It can also be done by hand
The number must contain all prime factors from 1-20 so first multiply all of them (2*3*..*19) then multiply again with some more factors till it contains all the other composite factors as well.

wulk18 · Jun 29, 2013

I have figure out that the problem was in the '^' operator. I expected it to be an exponent operator, but it wasn't! I wrote a separate function for doing exponent problems. I got the answer.

Now I want to know why my primenumber program runs too slow. Is it due to excessive recursion? How can I make it fast?

Here is my function which returns the nth prime factor.

Code:

int primenumber(int x) //user passes the 'x' i.e which primefactor he wants
{
if(x==1)  //if x is 1, return 2 as it is the first prime number
return 2;



int iii = (primenumber(x-1)) + 1;

for(int n = (x-1);n >= 1;n--)
{
int z;
z = iii%(primenumber(x-n));
if(z==0)
{iii++;
n=x;}

}

return iii;
}

harshilsharma63 · Jun 29, 2013

oh man, that's very unoptimized. Do that without recursion. Do it like: keep finding prime numbers until you have enough prime numbers.

vickybat · Jun 29, 2013

ico's brute force method is simple but isn't generalised. Try this. Its in java , but can easily ported to C++. Post back if you have any doubts and i can explain :

PHP:

public class lowestDivisible {
	

	private static int divisor;
	  
	  
	  public static boolean findNum (int n){
	    
	      for (divisor =2; divisor<=20;divisor++){
	          
	         int a = n % divisor;
	              if(a != 0){
	        	 
	        	return false;
	        	 
	         }
	           
	      }
	      return true;
	    }
	        
	   public static void main( String []args){
	        int m;
	        for ( m = 20; m < 500000000; m++ ) {
			 
			 if ( findNum(m) ) {
			 
			        break;
			 
			     }
			 
			}
			 System.out.println("The number is:" + m);
			 }
		}

rohitshubham · Jun 30, 2013

vickybat said:

ico's brute force method is simple but isn't generalised. Try this. Its in java , but can easily ported to C++. Post back if you have any doubts and i can explain :

PHP:

public class lowestDivisible {
    

    private static int divisor;
      
      
      public static boolean findNum (int n){
        
          for (divisor =2; divisor<=20;divisor++){
              
             int a = n % divisor;
                  if(a != 0){
                 
                return false;
                 
             }
               
          }
          return true;
        }
            
       public static void main( String []args){
            int m;
            for ( m = 20; m < 500000000; m++ ) {
             
             if ( findNum(m) ) {
             
                    break;
             
                 }
             
            }
             System.out.println("The number is:" + m);
             }
        }

yup, but his code was really simple.. just a bit more addition though would have made it very optimized like nesting the loop where he's checking for remainder ./* to lazy to write it/*

i would be more than pleased if you could give me the algorithm of the program..(i can make out a bit of recursion how was the number found... i mean it was moduled by each of the natural number separately . then how AND func was replaced???)moreover, i don't know java much... but looking at the code, i think you presumed the value to be less than 5000000...

vickybat · Jul 1, 2013

rohitshubham said:
yup, but his code was really simple.. just a bit more addition though would have made it very optimized like nesting the loop where he's checking for remainder ./* to lazy to write it/*
i would be more than pleased if you could give me the algorithm of the program..(i can make out a bit of recursion how was the number found... i mean it was moduled by each of the natural number separately . then how AND func was replaced???)moreover, i don't know java much... but looking at the code, i think you presumed the value to be less than 5000000...

My code is really simple mate and not at all difficult to understand.

Here are the steps:

* There is a method ( function) called findNum that takes the number (num) as an input parameter. Note that the return type of the method is a boolean and returns either a true or a false.

* The method has a for loop that iterates through 2 - 20, divides the number through the range in each iteration and checks if the remainder is zero or not. If any of the iterations is a non-zero remainder, the method returns false.

* If a number gets divided by all numbers from 2- 20 with zero remainder, it returns true.

* Now come to the main method. Here i run a calculated for loop for the number that is to be divided and passed as an argument in the findNum() method.

* I figured out the number and set a random large value. ( We can avoid this for loop here and go for a 'while', making it more generalised. I'll show you in a while.

).

* Then for each iteration, the method is called again and again( you can say recursive

) until it returns true, confirming that to be the desired number divisible through 2-20 without any remainder.

* Finally when true, it breaks out of the for loop and prints that number.

Here's the while version and its fully generalized. You can pass any number and check divisibility through any set of data.
We use while loops when the range of iterations isn't known.

PHP:

public class lowestDivisible {
	

	private static int divisor;
	  
	  
	  public static boolean findNum (int n){
	    
	      for(divisor =2; divisor<=20;divisor++){
	          
	         if(n % divisor != 0){
	        	 
	        	return false;
	        	 
	         }
	           
	       }
	      return true;
	     }
	        
	      
	    
	 public static void main( String []args){
	     int m =20;
		 while( findNum(m) == false) {
			 
			        m+=1;
			 }
			        
			 System.out.println("The number is:" + m);
			     }
		
			 
}

Removed some unwanted variables and added a while loop instead of for. See if you can make it even more optimized. Afterall in programming, ideas are shared so that the code keeps getting better and better.

P.S - If you are a C++ programmer, understanding java isn't difficult at all. Besides, the code i've written is extremely general and completely procedural.

rohitshubham · Jul 3, 2013

vickybat said:
My code is really simple mate and not at all difficult to understand. Here are the steps:

* There is a method ( function) called findNum that takes the number (num) as an input parameter. Note that the return type of the method is a boolean and returns either a true or a false.

* The method has a for loop that iterates through 2 - 20, divides the number through the range in each iteration and checks if the remainder is zero or not. If any of the iterations is a non-zero remainder, the method returns false.

* If a number gets divided by all numbers from 2- 20 with zero remainder, it returns true.

* Now come to the main method. Here i run a calculated for loop for the number that is to be divided and passed as an argument in the findNum() method.

* I figured out the number and set a random large value. ( We can avoid this for loop here and go for a 'while', making it more generalised. I'll show you in a while. ).

* Then for each iteration, the method is called again and again( you can say recursive ) until it returns true, confirming that to be the desired number divisible through 2-20 without any remainder.

* Finally when true, it breaks out of the for loop and prints that number.

Here's the while version and its fully generalized. You can pass any number and check divisibility through any set of data.
We use while loops when the range of iterations isn't known.

PHP:

public class lowestDivisible { private static int divisor; public static boolean findNum (int n){ for(divisor =2; divisor<=20;divisor++){ if(n % divisor != 0){ return false; } } return true; } public static void main( String []args){ int m =20; while( findNum(m) == false) { m+=1; } System.out.println("The number is:" + m); } }

Removed some unwanted variables and added a while loop instead of for. See if you can make it even more optimized. Afterall in programming, ideas are shared so that the code keeps getting better and better.

P.S - If you are a C++ programmer, understanding java isn't difficult at all. Besides, the code i've written is extremely general and completely procedural.

i only know C and a bit of pyhton :O

vickybat · Jul 3, 2013

rohitshubham said:
i only know C and a bit of python :O

Here you go in python:

PHP:

def test ():

    m =20
    while findNum(m) == False :
             
        m = m + 1
    print 'The number is' +' '+ str(m)


def findNum(n):

    for div in range (2,20):
	
	if n % div != 0:
                 
          return False
                 
    return True

test()

rohitshubham · Jul 3, 2013

vickybat said:

Here you go in python:

PHP:

def test ():

    m =20
    while findNum(m) == False :
             
        m = m + 1
    print 'The number is' +' '+ str(m)


def findNum(n):

    for div in range (2,20):
    
    if n % div != 0:
                 
          return False
                 
    return True

test()

now that's neat.
you know python is definitely the neatest language I've ever encountered . i mean it's hassle free and even a non programmer will easily understand it.
and i presume that you are in college.. which one?

Chaitanya · Jul 4, 2013

Actually you are trying to find a no that is product of highest powers of all primes below n..
For instance..
If you select n=25
primes are 2, 3, 5, 7, 11, 13, 17, 19, 23

No. you require is prod of highest powers of all primes less than or equal to n

means ans = 2^4 * 3^2 * 5^2 * 7 * 11 * 13 * 17 * 19 * 23
here 2^4 =16 & 2^5 =32 so 32 is not possible
next 3^3 = 27 again greater than 25 so 3^2
7^2=49 > 25 so 7^1 & eventually all others..

PHP:

//Program for generating no divisible by all no between 1 & n
#include<iostream>
#include<cstdlib>

using namespace std;

long sieve[100000000],primes[5000000];
void primegen(long);
int main(void)
	{
		long no,i,j;
		double LCM=1;
		system("cls");
		//inputting the no..
		cout<<"\n\tEnter the no..: ";
		cin>>no;
		primegen(no);

		//checking for highest possible power of a particular prime
		for(i=0;primes[i]!=0;i++)
            {
                for(j=primes[i]; ;j*=primes[i])
                    if(j>no)
                        break;
                LCM*=(1LL*j/primes[i]);
            }
        //displaying op
        cout<<"\n\nRequired no. is : "<<LCM<<"\n\n\n";
		system("pause");
	}

//fn for generating prime nos..
void primegen(long n)
    {
        long i,j,sq,k=0;
        for(i=2;i<=n;++i)
            if(!sieve[i])  //proceed only if no. is not already marked
                {
                    primes[k++]=i;        //store the prime no.
                    for(j=i*i;j<=n;j+=i)  //mark all multiples of a prime
                        sieve[j]=1;
                }
    }

vickybat · Jul 4, 2013

^^ Your code throws the following error when compiled:

Line 22: error: use of C99 long long integer constant

Chaitanya · Jul 4, 2013

Which compiler are you using??

*i.imgur.com/3hW7d5a.jpg

worked for me though..

vickybat · Jul 4, 2013

Chaitanya said:
Which compiler are you using??

*i.imgur.com/3hW7d5a.jpg

worked for me though..

Yeah i can see that. I don't program in c or c++, thus used an online compiler to run your code ( codepad.org). C++ code - 43 lines - codepad
I can see your screenshot and it seems fine.

It would be great if you can write a more clear and concise algorithm for your code, so that it will be easier for everyone to comprehend and understand.

rohitshubham · Jul 4, 2013

vickybat said:

Here you go in python:

PHP:

def test ():

    m =20
    while findNum(m) == False :
             
        m = m + 1
    print 'The number is' +' '+ str(m)


def findNum(n):

    for div in range (2,20):
    
    if n % div != 0:
                 
          return False
                 
    return True

test()

i ran the code now and the Output is "the number is 20"
first it gave the error that it's not intended properly. but after indentation also it gives that the number is 20

vickybat · Jul 4, 2013

rohitshubham said:
i ran the code now and the Output is "the number is 20"
first it gave the error that it's not intended properly. but after indentation also it gives that the number is 20

The indentation was a bit off. Try now:

PHP:

def test ():

    m =20
    while findNum(m) == False :
             
        m = m + 1
    print 'The number is' +' '+ str(m)


def findNum(n):

   for div in range (2,20):
    
      if n % div != 0:
                 
          return False
                 
   return True

test()

The "return true" statement's indentation should be exactly equal with the for loop, in the findNum() function.
That means, when the divisibility test passes, it should return True.

*codepad.org/qDvGbVEa

Try the code in your local python interpreter. The online interpreter throws timeout errors for large range.

*codepad.org/a1Z799ja

Chaitanya · Jul 4, 2013

vickybat said:
It would be great if you can write a more clear and concise algorithm for your code, so that it will be easier for everyone to comprehend and understand.

Well for getting my code first read Sieve of Eratosthenes - Wikipedia, the free encyclopedia & grab concepts here *www.thinkdigit.com/forum/programming/173227-find-sum-prime-numbers-till-2-million.html#post1899201

Basically I'm generating list of prime nos. less than (input) n here..

then I store them in array primes..

now get back to main..
here I'm checking for highest possible power of a given prime no. less than (input) n

any no.that is divisible by all nos btwn 1-10 is a LCM of all these nos.

concept is that no. that is divisible by all from 1-10 must be divisible by all primes(greatest power of prime less than no.)

PHP:

for(i=0;primes[i]!=0;i++) 
            { 
                for(j=primes[i]; ;j*=primes[i]) 
                    if(j>no) 
                        break; 
                LCM*=(1LL*j/primes[i]); 
            }

dry run :
suppose no=10
prime[0]=2;

inner loop :
init : j=2,
cond : 2>10(false)
update : j=j*prime : j=2*2

j=4
cond : 4>10(false)
update : j=4*2

j=8
cond : 8>10 (false)
update : j=8*2

j=16
cond : 16>10 (true) , break;

now greatest power of 2 less than 10 was j/prime[0] (16/2)

hence reqd no at end of 1st iteration of outer loop is 8(highest power of 2).

nxt no is 3

3<10 true
3^2(i.e 9)<10 true.
3^3(i.e 27)<10 false

hence reqd power of 3 is 9.

& so on..

rohitshubham · Jul 4, 2013

vickybat said:
The indentation was a bit off. Try now:

PHP:

def test (): m =20 while findNum(m) == False : m = m + 1 print 'The number is' +' '+ str(m) def findNum(n): for div in range (2,20): if n % div != 0: return False return True test()

The "return true" statement's indentation should be exactly equal with the for loop, in the findNum() function.
That means, when the divisibility test passes, it should return True.

Python code - 20 lines - codepad

Try the code in your local python interpreter. The online interpreter throws timeout errors for large range.

Python code - 20 lines - codepad

nope,

still not running.. ideone says time limit exceeded while python 2.6 on my computer does not produce any output even after few minutes.
OKAY it took 15 minutes on my PC to complete the code(not sure if my PC is slow or the code). . mate, companies will kick me out for compiling this question in 15 minutes. Let's try a better algorithm

Chaitanya · Jul 4, 2013

have you tried my program?? Post

Have you understood my method??
try it in python..

C++ program running too slow

Right off the assembly line

Chosen of the Omnissiah

The Black Waltz

Right off the assembly line

DIY FTW!

I am the night...I am...

Ambassador of Buzz

I am the night...I am...

Ambassador of Buzz

I am the night...I am...

Ambassador of Buzz

Cyborg Agent

I am the night...I am...

Cyborg Agent

I am the night...I am...

Ambassador of Buzz

I am the night...I am...

Cyborg Agent

Ambassador of Buzz

Cyborg Agent