Prime - large numbers

Hy guys, Im back with the same problem.

I have to calculate how many prime no are between 1 - 10^7, and also to print how many of them have the sum of digits equal to 14.

Again my code works only for numbers up to 100,000. if I try to set i to go through 10,000,000, it takes like 30 minutes to respond.

Solutions ?

10x



#include <iostream>

using namespace std;

int sumOfDigits(int x)  // CALC SUM OF DIGITS
{
    int r, sum=0;
    while(x!=0)
    {
        r = x%10;
        x=x/10;
        sum+=r;
    }

    return sum;
}

int prim(int x) // RETURNS 1 IF PRIME, 0 IF IS NOT
{
   int v = 1;
   for(int i = 2; i<=(x/2);i++)
   {
       if(x%i == 0) v = 0;
   }
   return v;
}

int main()
{
    int i=18 // BECAUSE I'VE CHECKED FIRST 17 NO. 
    int contPrim = 7 // BECAUSE I'VE FOUND 7 PRIME NO.
    int contSum = 0;
    while(i<10000000)
    {
       if((i&0) || (i%3==0) || (i%5==0) || (i%7==0) || (i%11==0) || (i%17==0) ) i+=1;
            else if(prim(i)) {
                                contPrim+=1;
                                if(sumOfDigits(i)==14) contSum+=1;
                                i+=1;
                             } else i+=1;

    }

    cout << "there are " << contPrim << " prime numbers \n and " << contSum <<" have the sum of digits equal to 14. "<< endl;
}

Last edited on

xgeutzu (25)

SOLVED! running time: 26s

#include <iostream>
#include <cmath>

bool is_prime(int num);

int sumOfDigits(int x);

int main(void)
{
    int sumy = 0, prime = 7;
    const int PRIME_LIMIT = pow(10, 7);

    for (int i = 19; i < PRIME_LIMIT; i+=2)
    {
        if ( is_prime(i) )
        {
            prime++;
            if (sumOfDigits(i) == 14) sumy+=1;
        }
    }

    std::cout << "no of prime is " << prime << "\n and from them " << sumy << " has sumOfDigits = 14";

    return 0;
}

bool is_prime(int num)
{
    if (num < 2)
        return false;

    for (int i = 2; i <= (int)sqrt(num); i++)
    {
        if (num % i == 0)
            return false;
    }
    
    return true;
}

int sumOfDigits(int x)
{
    int n, r, sum=0;

    while(x!=0)
    {
        r = x%10;
        x=x/10;
        sum=sum+r;
    }

    return sum;
}

anup30 (968)

6 sec

#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int i);
bool is_count14(int i);

int main () {
	int val =1e7;
	int count =1; // 2,
	int count14=0; 
	for(int i=3; i<=val; i++){
		if( is_prime(i) ) {
			count++;
			if( is_count14(i) ) {
				count14++;
			}
		}
		
	}	
	
	cout << "Primes between 2 and " << val << " is " << count << endl;
	cout << "digit add 14 = " << count14 << endl;
	
	return 0;
}

bool is_prime(int j) {
	bool b= true;
	int k= sqrt(j);
	for(int i=2; i<= k; i++  ) {
		if(j%i==0) {
			b= false;
			break;
		}
	}
	return b;
}

bool is_count14(int k) {
	int n=0;
	do {
		n+= k%10;
		if(n>14) break;
		k /= 10;
	} while (k>0);
	
	if(n==14) return true;
	else return false;
}

PCrumley48 (173)

Could speed things up wit a couple of changes:

in int sumOfDigits(int x):

1
2

//change   while(x!=0) to
    while(x!=0 && sum < 14) // only sum digits until equal or greater than 14

in int prim(int x):

int prim(int x) // RETURNS TRUE IF PRIME, FALSE IF IS NOT
{
  int v = 1;
 
   //for(int i = 2; i<=(x/2);i++)

   for (int i = 3; i * i <= x && v; i +=2) // only check odd numbers, and only until a factor is found.
   {
      v = (x % i != 0);
   }
   return v;
}

I don't think this is necessary:

if((i&0) || (i%3==0) || (i%5==0) || (i%7==0) || (i%11==0) || (i%17==0) ) i+=1;

(in fact, ( i & 0 ) will always be false for non-zero integers, so none of the other comparisons are done)

Could make another small change - doesn't have a lot of effect, though, but probably more readable, don't have to figure out if or why i is incremented twice, and same as prim() only need to check odd numbers: (start out with i as an odd number, naturally)

           else if(prim(i)) {
                                contPrim+=1;
                                if(sumOfDigits(i)==14) contSum+=1;
                              // take this out:  i+=1;
                             } // and this: else
                             i+=2;

PCrumley48 (173)

Also, and I'm not going to post code for this:

If you modify sumOfDigits, you can do:

contSum += sumOfDigits(i);

in line 40.

sumOfDigits just has to return 1 for == 14, 0 for != 14. . .

Last edited on

PCrumley48 (173)

4.414 Seconds Debug mode, 3.322 .exe file:

#include <iostream>
#include <ctime>

using namespace std;

int sumOfDigits(int x)
{
	int r, sum=0;
	while(x!=0 && sum < 15 )
	{
		sum += x%10;
		x=x/10;
	}
	return sum == 14;
}

int prim(int x)
{
	int v = 1;

	for(int i = 3; i*i <= x && v;i+=2)
		if(x%i == 0) v = 0;
	return v;
}

int main()
{
	int i=3;
	int contPrim = 2;
	int contSum = 0;
	clock_t t0, t1;
	t0 = clock();
	while(i<1000)
	{
		if(prim(i))
		{
			contPrim ++;
			contSum += sumOfDigits(i);
		}
		i+=2;
	}
	t1 = clock();
	cout << "There are " << contPrim << " prime numbers \n\nand " << contSum <<" have the sum of digits equal to 14.\n\n";
	cout << "\nTime Test:\n" << "Running Time\t"<< double(t1-t0) / CLOCKS_PER_SEC << " sec\n";

	system("Pause");
	return 0;
}

Last edited on

anup30 (968)

@PCrumley48, your digit count to 14, is wrong.
i.e. in 1 to1000 there are 17 such numbers. but your last code says 14 such numbers.

PCrumley48 (173)

@PCrumley48, your digit count to 14, is wrong.
i.e. in 1 to 1000 there are 17 such numbers. but your last code says 14 such numbers.

Well. . .that's strange. I don't see how, but I'll have to try to find out which three are missing and why!

Thanks for pointing that out :(

Well, got to take change < 14 to < 15. . . in int sumOfDigits(int x)

Last edited on

Topic archived. No new replies allowed.

C++

Forum

Prime - large numbers