Better Solution to Find prime numbers in interval [1000,9999] where the sum of first and second

Question

I want to Find prime numbers in interval [1000,9999] where the sum of first and second digits is equal to sum of third and fourth digits of the number.

For example 3517 is prime number and 3 + 5 = 1 + 7

My solution is the following:

for (int i = 1001; i <= 9999; i += 2)
{
     if (NumberOfDivisorsOf(i) == 2)
     {
        string x = i.ToString();
        int n1 = Convert.ToInt32(x[0]); 
        int n2 = Convert.ToInt32(x[1]); 
        int n3 = Convert.ToInt32(x[2]); 
        int n4 = Convert.ToInt32(x[3]); 

         if ((n1 + n2) == (n3 + n4))
              Console.WriteLine(i);
      }
}

NumberOfDivisorsOf method looks like this:

static int NumberOfDivisorsOf(int a)
{
    int count = 2;
    int i = 2;

    for (; i < a/i ; i++)
    {
       if (a / i * i == a)
           count += 2;
    }

    if (i * i == a)
        count++;

    return count;
}

I think NumberOfDivisorsOf method is fine and improvement needs to the solution itself.

I don't want to use LINQ. I want to get them with simple steps..

EDIT:

Depending On OMG answer I improve code as shown below:

for (int i = 1001; i <= 9999; i += 2)
{
    if (Isprime(i))
    {
       int n1 = i / 1000;
       int n2 = (i % 1000) / 100;
       int n3 = (i % 100) / 10;
       int n4 = i % 10;

       if ((n1 + n2) == (n3 + n4))
       {
          Console.WriteLine(i);
       } 
    }
}

I changed NumberOfDivisorOf method to IsPrime method:

static bool Isprime(int n)
{
    if (n == 2)
       return true;
    if (n == 3)
       return true;
    if ((n % 2) == 0)
       return false;
    if (n % 3 == 0)
        return false;

    int i = 5;
    int w = 2;

    while (i * i <= n)
    {
        if (n % i == 0)
           return false;

           i += w;
           w = 6 - w;
    }

    return true;
}

EDIT:

Depending on Siye answer I changed my code as shown below (it made executions speed 3x faster)

for (int i = 1001; i <= 9999; i += 2)
{
    int n1 = i / 1000;
    int n2 = (i % 1000) / 100;
    int n3 = (i % 100) / 10;
    int n4 = i % 10;

    if ((n1 + n2) == (n3 + n4))
    {
       if (Isprime(i))
       {
            Console.WriteLine(i);
       }
    }
}

`int n1 = i.ToString()[0]` is wrong. That will give you the value of the `char` at that index. `(int)'0' !=0` You need to either use `int.Parse` or subtract `'0'`... Though I suppose the math would still work out, you may as well be exact — pinkfloydx33, Jun 03 '18 at 14:32

OmG · Accepted Answer · 2018-06-03T14:47:07.973

0

To find the prime number efficiently, there exist some good solutions(such as this). To better your approach to find the sum, it would be better using % or using .ToString() just once in your code as the overhead of it can effect on the performance in high scale.

To use % you can find them by:

int n4 = i % 10;
int n3 = (i % 100) / 10;
int n2 = (i % 1000) / 100;
int n1 = (i % 10000) / 1000;

Also, instead of NumberOfDivisorsOf it would be better to use is_prime by using break in the loop when you found the number is prime.

edited Jun 03 '18 at 14:47

answered Jun 03 '18 at 14:29

OmG

18,337
10
57
90

you are right, changing NumberOfDivisorOf method dramatically reduced execution time. – Jun 03 '18 at 14:51

score 0 · Answer 2 · answered Jun 03 '18 at 14:53

0

for (int i = 1001; i <= 9999; i += 2)
{
    int n1 = i.ToString()[0];
    int n2 = i.ToString()[1];
    int n3 = i.ToString()[2];
    int n4 = i.ToString()[3];
    if ((n1 + n2) == (n3 + n4)) {
        if (NumberOfDivisorsOf(i) == 2)
            Console.WriteLine(i);
        i = (i / 10 + 1) * 10;  // A little improvement
        continue;
    }
    if ((n1 + n2) > (n3 + n4)) {
        i = (i / 10 + 1) * 10;
        continue;
    }   
}

This may make a little improvment.

By the way, Sieve of Eratosthenes may improve the performance of method NumberOfDivisorsOf.

answered Jun 03 '18 at 14:53

Siye

39
8

Getting digits before and comparing their sums reduce the execution time but i =( i / 10 + 1) * 10 not works.. – Jun 03 '18 at 15:06
@A.M uhh... I don't know. I just try to skip some needless steps in the loop. If the sum of first and second digits is less than the sum of third and fourth digits. We don't need to add 2 to the fourth digits, because the latter sum will always be greater than the first sum until the third digit changes. We can skip these and add 1 to the third number and make the fourth number equal to 0. I think it may work theoretically. – Siye Jun 03 '18 at 15:33

Better Solution to Find prime numbers in interval [1000,9999] where the sum of first and second

2 Answers2