Printing prime numbers between 100 to 1000 whose digit sum equals to 19

Question

I have this problem . I have written the code for the same but I am unable to find the error where I am doing mistake. It is printing 100 as output nothing else.

package practicepkg;

import java.util.Scanner;

public class PrimeNumber {

    public static void main(String[] args) {
        System.out.println("Enter the number to check");
        Scanner in = new Scanner(System.in);
        //taking input for 1000
        int number =  in.nextInt();
        int count=0;
        int k,num=100,sum=0;
        //running loop from 100 to till user input(1000)
        for(k=100;k<=number;k++)
        {
            //loop for checking prime number
             for(int i=2;i<(int)(Math.sqrt(number));i++)
                    {
                        if(k%i==0)
                        {
                            count+=1;
                            
                        }
                        //here only taking prime numbers
                        if(count==0)
                        {
                            num=k;
                            //using while loop to calculate sum
                            while(num!=0)
                            {
                                sum=sum+num%10;
                                num=num/10;
                            }
                            //comparing and printing the actual prime number value for k
                            if(sum==19)
                            System.out.println(k);
                        }
                        //resetting the count value to zero for next iteration
                        count=0;    
                                            
                     }
                                     
        }
        
    }
}  

Answer 1

You are looking at numbers between 100 and 1000. In that range, all numbers ending in an even digit, or ending with 5, are not prime so you don't even need to bother checking them. Prime numbers can only end in 1, 3, 7 or 9 within that range.

That gives you pseudocode something like:

for (base <- 100; base < 1000; step 10)
  test(base + 1)
  test(base + 3)
  test(base + 7)
  test(base + 9)
endfor

This can be further refined by checking the digit sum of base before prime testing. You only need bother to check further where the digit sum of base is one of (19 - 1), (19 - 3), (19 - 7) or (19 - 9). That means you can step through the range 100 to 1000 only looking at every tenth number, calculating its digit sum and checking either none or just one of the potential primes in the ten numbers following.

You could shave off some more time by noticing that the smallest three digit number with a digit sum of 19 is 199, so you could start base at 190 instead of at 100.

Answer 2

Using your basic brute force approach, the sum should be reset to 0 for each prime number and we need to calculate the sum after we have completed checking if the number is prime or not.

public static void main(String[] args) {
    System.out.println("Enter the number to check");
    Scanner in = new Scanner(System.in);
    //taking input for 1000
    int number =  in.nextInt();
    int count=0;
    int k,num=100,sum=0;
    //running loop from 100 to till user input(1000)
    for(k=100;k<=number;k++)
    {
        //loop for checking prime number
         for(int i=2;i<(int)(Math.sqrt(number));i++)
         {
             if(k%i==0)
             {
                 count+=1;
             }                   
         }
         //This should be outside the loop that checks the number for prime
         if(count==0)
         {
             //Sum should be reset for each new prime number
             sum=0;
             num=k;
             //using while loop to calculate sum
             while(num!=0)
             {
                 sum=sum+num%10;
                 num=num/10;
             }
             //comparing and printing the actual prime number value for k
             if(sum==19)
                 System.out.println(k);
         }
         //resetting the count value to zero for next iteration
         count=0;            
    }
    
}

Edit: Optimal solution to the above problem. Thanks to @D George to point it out

public static void main(String[] args) {
    System.out.println("Enter the number to check");
    Scanner in = new Scanner(System.in);
    //taking input for 1000
    int number =  in.nextInt();
    boolean flag = false;
        int k,num=100,sum=0;
        //running loop from 100 to till user input(1000)
        for(k=100;k<=number;k++)
        {
            //resetting the flag value to false for next iteration
             flag = false;
            //loop for checking prime number
             for(int i=2;i<(int)(Math.sqrt(number));i++)
             {
                 if(k%i==0)
                 {
                     flag=true;
                     break;
                 }                   
             }
             //This should be outside the loop that checks the number for prime
             if(!flag)
             {
                 //Sum should be reset for each new prime number
                 sum = 0;
                 num = k;
                 //using while loop to calculate sum
                 while(num!=0)
                 {
                     sum += num%10;
                     num /= 10;
                 }
                 //comparing and printing the actual prime number value for k
                 if(sum==19) {
                     System.out.println(k);
                 }
             }

        }
 }