C++ program running too slow

W

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;

}

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;
	}

C

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.

W

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;
}

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

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);
			 }
		}

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

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.

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

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()

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?

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;
                }
    }

^^ Your code throws the following error when compiled:

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

Which compiler are you using??

*i.imgur.com/3hW7d5a.jpg

worked for me though..

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.

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

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

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

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

have you tried my program?? Post

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

rohitshubham said:
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

Yup its taking a lot of time in python. My earlier Java code takes just over a second to complete. Dunno why the same logic is so slow in python.
Try copy pasting my java code in an eclipse or netbeans ide. It will generate output in just over a second. Divisibility checks are the slowest form of computation.

That said, chaitanya's code is extremely optimised. That's because he uses the sieve of eratosthenes algorithm to generate primes and stores them in an array.
The SOE algorithm does not has any form of divisibility check to determine primes. It relies on striking out the multiples of prime numbers in each iteration and the numbers left out are primes.No divisibilty check per iterartion here.

Then he compares the highest power of each prime with the largest range, then multiplies them in each iteration. So the LCM of all these numbers gives the resultant output.

I'm trying a simplified boolean function in java that does the same thing but much simplified. Didn't quite get the time today, but will post soon as its complete.

Chaitanya's method is highly optimized and even OP should consider this in C++.

P.S= What are your PC specs??

vickybat said:
Yup its taking a lot of time in python. My earlier Java code takes just over a second to complete. Dunno why the same logic is so slow in python.
Try copy pasting my java code in an eclipse or netbeans ide. It will generate output in just over a second.

Noob question which one is java code & which one is python?? :-D

How to compile python ??

somewhere read that although python is simple & easy but is slower as compared to C/C++ (dunno abt it's authenticity)

Chaitanya said:
Noob question which one is java code & which one is python??
How to compile python ??

somewhere read that although python is simple & easy but is slower as compared to C/C++ (dunno abt it's authenticity)

Post # 8 - Java
Post # 10 -python

Well in java its fast enough but taking a lot slower in python. Couldn't figure out why though.
Python is an interpreter based and dynamically typed language. Its not compiled as a whole but interpreted line by line at runtime, just like javascript, where browsers are interpreters.

Python is simple and easy but i kind of dislike the indentations. One has to be very careful there. That said, both java and python have different usage.
For example, python is used to build web crawlers ( search engines) and kind of forms the building block.

String methods are highly efficient in python and has the easiest implementation. Pattern matching and usage of regular expressions is ideal in python, which are used in several validations in search engines and several other applications like email clients. Every language has a different usage pattern and has their drawbacks in certain scenarios. The python code here will be a solid example.

That said, python is as authentic as c or c++. Coding a search engine in c++ is extremely tedious. Python is used for its simplicity in certain scenarios. Similarly game engines are build mostly in C++ where more low level control is required.

I'm not a programmer but have recently developed great interest in it and open to learn new things. I'm an electronics and telecomm graduate btw. Never had any experience in programming during college, but loving it now. :))

vickybat said:
I'm not a programmer but have recently developed great interest in it and open to learn new things. I'm an electronics and telecomm graduate btw. Never had any experience in programming during college, but loving it now.

Lovely info..

Mee too.. I'm not from CS/IT but have keen interest in prog. will learn Python & Java altho python would be of greater preference.. :-D

Any tips/guides. Any good study material ?

vickybat said:
String methods are highly efficient in python and has the easiest implementation. Pattern matching and usage of regular expressions is ideal in python, which are used in several validations in search engines and several other applications like email clients. Every language has a different usage pattern and has their drawbacks in certain scenarios. The python code here will be a solid example.

That said, python is as authentic as c or c++. Coding a search engine in c++ is extremely tedious. Python is used for its simplicity in certain scenarios. Similarly game engines are build mostly in C++ where more low level control is required.

I was planning such hard $hit on c++ ..
But seems python has paved a way out for me

Chaitanya said:
Lovely info..
Mee too.. I'm not from CS/IT but have keen interest in prog. will learn Python & Java altho python would be of greater preference..
Any tips/guides. Any good study material ?

I was planning such hard $hit on c++ ..
But seems python has paved a way out for me

If you want to learn python, then join here:

*www.udacity.com/

Take the "intro to computer science" class. Its completely about python. Btw, i'm almost halfway now. :))

vickybat said:
Yup its taking a lot of time in python. My earlier Java code takes just over a second to complete. Dunno why the same logic is so slow in python.
Try copy pasting my java code in an eclipse or netbeans ide. It will generate output in just over a second. Divisibility checks are the slowest form of computation.

That said, chaitanya's code is extremely optimised. That's because he uses the sieve of eratosthenes algorithm to generate primes and stores them in an array.
The SOE algorithm does not has any form of divisibility check to determine primes. It relies on striking out the multiples of prime numbers in each iteration and the numbers left out are primes.No divisibilty check per iterartion here.

Then he compares the highest power of each prime with the largest range, then multiplies them in each iteration. So the LCM of all these numbers gives the resultant output.

I'm trying a simplified boolean function in java that does the same thing but much simplified. Didn't quite get the time today, but will post soon as its complete.

Chaitanya's method is highly optimized and even OP should consider this in C++.

P.S= What are your PC specs??

it's ancient :0
like P4 and stuff
even triend it on my old lappy and it gave results in 10 min . its AMD m3000+ 64 bit dual core, it was working for 50%cpu constantly

rohitshubham said:
it's ancient :0
like P4 and stuff
even triend it on my old lappy and it gave results in 10 min . its AMD m3000+ 64 bit dual core, it was working for 50%cpu constantly

These are the culprits then. I have a quad core i5 750. :))

Anyways, run chaitanya's code in your machine and post back here about its execution times.

vickybat said:
Anyways, run chaitanya's code in your machine and post back here about its execution times.

Yeah mee too..
Wanna see how optimize it is for older & Slower sys..

Chaitanya said:
Yeah mee too..
Wanna see how optimize it is for older & Slower sys..

it's giving errors..(it's CPP..isn't it??)

^Yeah its c++ code.
Which compiler are you using??
borland/turbo c++ are bit too archaic for the code.

I brute forced and checked if the number (starting with 19*20=380, wild guess) it was divisible by 11 through 18 and incremented it by 19*20=380. Got my answer under 1 sec. in Python.

Chaitanya said:
^Yeah its c++ code.
Which compiler are you using??
borland/turbo c++ are bit too archaic for the code.

turbo c++

use Code::blocks with mingw

Chaitanya said:
use Code::blocks with mingw

i am using ideone but the results are not correct.

Chaitanya said:
use Code::blocks with mingw

i am using ideone but the results are not correct.

^^LOL found the culprit.
Change the variable type of "LCM" to long from double

Chaitanya said:
^^LOL found the culprit.
Change the variable type of "LCM" to long from double

Yup, it's working now

but i want stats on my computer and it's not running on TC++, plz suggest me some other compiler.(preferably small one)

Smaller ??
try Devc++ ... It's old & no current support for it + doesn't work on windows 8

But is good enough for the job. ;-)

Chaitanya said:
Smaller ??
try Devc++ ... It's old & no current support for it + doesn't work on windows 8

But is good enough for the job.

yup, it ran perfectly and ran within .1 seconds

rohitshubham said:
Yup, it's working now
but i want stats on my computer and it's not running on TC++, plz suggest me some other compiler.(preferably small one)

Please stop using turboC. Its will lead you to doom. use Code::Blocks or eclipse or Visual Studio.

rohitshubham said:
yup, it ran perfectly and ran within .1 seconds

Nice.. but better get
1.Code Blocks

2.Eclipse

3.VS

Chaitanya said:
Nice.. but better get
1.Code Blocks

2.Eclipse

3.VS

harshilsharma63 said:
Please stop using turboC. Its will lead you to doom. use Code::Blocks or eclipse or Visual Studio.

which is better VS or codeblocks.?
i mean which can create more interactive programs easily?
and what's difference between Codeblocks setup and codeblocks_mingw setup apart from huge size difference??

rohitshubham said:
which is better VS or codeblocks.?
i mean which can create more interactive programs easily?
and what's difference between Codeblocks setup and codeblocks_mingw setup apart from huge size difference??

Dunno about VS but code blocks is excellent...(code highlighting, code auto-completion ... etc..)

Code blocks is a IDE..
code blocks mingw is IDE + Compiler..

Z

How to increase program without coding

zeeshanaayan07 said:
How to increase program without coding

What do u want??