Find whether natural number is composite or prime

[Akimbas Akimbasas]

Hello, I need to write a program that finds out whether the number is prime or composite, if the number is composite, the program should write what are the divisors and how many are there. If the number is prime, it need to say that he number is prime.

import java.util.Scanner;
import java.lang.Math;
public class for__ {
    public void Skaiciavimai() {
        Scanner input = new Scanner (System.in);
        System.out.println("Write a number");
        int x = input.nextInt();
        int quantity = 0; 
        int divisor = 0;  
        for (int i = 1; i <= x; i++) {
        if (x % i == 0) {
            quantity++;
            divisor = i; 
            System.out.println("The number is composite, his divisors are "  + divisor);   
        }          
          else {
            System.out.println("The number is prime.");
    }
    }
System.out.println("There are this many divisors: " + quantity);
}
}

The problem is that console spits ous:
Write a number
10
The number is composite, his divisors are 1
The number is composite, his divisors are 2
The number is prime.
The number is prime.
The number is composite, his divisors are 5
The number is prime.
The number is prime.
The number is prime.
The number is prime.
The number is composite, his divisors are 10
There are this many divisors: 4


I see that the program tries x % i == 0 , and if it succeeds, then it writes that the number is composite, else it writes that it is prime. How should I go about fixing this ?

[Tony Docherty]

The line printing out "The number is prime" shouldn't be inside the for loop as you can only tell if a number is prime after the for loop has completed.

[Akimbas Akimbasas]

Tony Docherty wrote:The line printing out "The number is prime" shouldn't be inside the for loop as you can only tell if a number is prime after the for loop has completed.

If I try to make it something like this:

import java.util.Scanner;
import java.lang.Math;
public class for__ {
    public void Skaiciavimai() {
        Scanner input = new Scanner (System.in);
        System.out.println("Write a number");
        int x = input.nextInt();
        int quantity = 0; 
        int divisor = 0;  
        for (int i = 1; i <= x; i++) {
        if (x % i == 0) {
            quantity++;
            divisor = i;                       
            System.out.println("The number is composite, his divisors are:"  + divisor);   
        }          
          
    }
    System.out.println("There are this many divisors: " + quantity);
        
          else {
            System.out.println("The number is prime.");
    }
}
}

It writes: 'else' without 'if'

[Tony Docherty]

Why do you think you still need the 'else'?
What test do you think you need to use to restrict the line to only print out if it is a prime number?

[Akimbas Akimbasas]

Tony Docherty wrote:Why do you think you still need the 'else'?
What test do you think you need to use to restrict the line to only print out if it is a prime number?

    import java.util.Scanner;  
    import java.lang.Math;  
    public class for__ {  
        public void Skaiciavimai() {  
            Scanner input = new Scanner (System.in);  
            System.out.println("Write a number");  
            int x = input.nextInt();  
            int quantity = 0;   
            int divisor = 0;    
            for (int i = 1; i <= x; i++) {  
            if (x % i == 0) {  
                quantity++;  
                divisor = i;   
                System.out.println("The number is composite, his divisors are "  + divisor);     
            }            
              
        }  
        System.out.println("There are this many divisors: " + quantity);  
        for (int i = 2; i < x; i++) {  
            if (x % i != 0) {  
                System.out.println("The number is a prime");
                
        }  
    
    }  
    }  
}

I guess else is a bit abstract, then how about this ? But again, the problem is "The number is a prime" it will loop the number of times the if statement is = true, what I should write in if then ?

[Tony Docherty]

You already have a variable which, once the for loop completes, tells you whether the number was prime or not.

[Ulf Dittmer]

As an aside, you shouldn't start the for loop at 1, and it shouldn't run until "i == x" - even a prime numbers is divisible by 1 and by itself.

[Akimbas Akimbasas]

Tony Docherty wrote:You already have a variable which, once the for loop completes, tells you whether the number was prime or not.

    import java.util.Scanner;  
    import java.lang.Math;  
    public class for__ {  
        public void Skaiciavimai() {  
            Scanner input = new Scanner (System.in);  
            System.out.println("Write a number");  
            int x = input.nextInt();  
            int quantity = 0;   
            int divisor = 0;    
            for (int i = 1; i <= x; i++) {  
            if (x % i == 0) {  
                quantity++;  
                divisor = i;                        
                System.out.println("The number is composite, his divisors are: "  + divisor); 
            }                  
        }         
        System.out.println("There are this many divisors: " + quantity);  
        if ( quantity <= 2) {
            System.out.println("The number is prime");
            
    }  
    }  
}

How about this then ? Still there is problem, even if it's a prime(7) number, I get:
The number is composite, his divisors are: 1
The number is composite, his divisors are: 7
There are this many divisors: 2
The number is prime

The first three lines are unwanted, how should I let program understand that if it's prime, it should skip those three lines ?

[Akimbas Akimbasas]

Ulf Dittmer wrote:As an aside, you shouldn't start the for loop at 1, and it shouldn't run until "i == x" - even a prime numbers is divisible by 1 and by itself.

My second loops does just that.(in the code, which is above the most recent.) But it doesn't make sense(I mean the results of code), I guess should think about what to write more.

[Tony Docherty]

The first three lines are unwanted, how should I let program understand that if it's prime, it should skip those three lines ?

All numbers are divisible by 1 and themselves so are you sure you even need to print this out for composite numbers.

[Akimbas Akimbasas]

Tony Docherty wrote:

The first three lines are unwanted, how should I let program understand that if it's prime, it should skip those three lines ?

All numbers are divisible by 1 and themselves so are you sure you even need to print this out for composite numbers.

Well I'm not sure, the task says "find divisors", that's it. Then maybe I should try to write a program, that does not include numbers 1 and itself, and then see if it's possible to do otherwise.

[Akimbas Akimbasas]

import java.util.Scanner;    
    import java.lang.Math;    
    public class for__ {    
        public void Skaiciavimai() {    
            Scanner input = new Scanner (System.in);    
            System.out.println("Write a number");    
            int x = input.nextInt();    
            int quantity = 0;     
            int divisor = 0;      
            for (int i = 2; i < x; i++) {  
            if (x % i == 0) {    
                quantity++;    
                divisor = i;                          
                System.out.println("The number is composite, his divisors are: "  + divisor);   
            }                                
        }                  
        if (quantity >= 1) {
            System.out.println("There are total of " + quantity + " divisors.");
        }
        if (quantity < 1) {
            System.out.println("The number is a prime.");
        }
    }
}
  

Without writing the 1 and the number itself as divisors, it seems to work. I guess this will do, because I don't see any need to write that any number is divisible by 1 and itself. Thanks for the help.

[Winston Gutkowski]

Akimbas Akimbasas wrote:My second loops does just that.(in the code, which is above the most recent.) But it doesn't make(I mean the results of code), I guess should think about what to write more.

Bingo. And furthermore, you should ALWAYS think before you write even one line of code.

Tip for you: The real problem here is not simply to find out if a number is prime - there are lots of ways to do it by brute force - it's to work out the correct steps for doing so.

So, assuming you're going to use a "progressive factor check" - and there's absolutely nothing wrong with that - a couple more questions for you, that may help you to get to the solution:
1. You now know that you shouldn't start at 1, because ALL numbers divide by 1; but where do you end? ie: what is the largest factor you need to check?
2. Do you think you need to check ALL factors in the range? For example: if I already know that my number n doesn't divide by either 2 or 3, is there any point in me checking if it divides by 6? And if not, which factors do you think make most sense to check?

HIH

Winston

[Akimbas Akimbasas]

Winston Gutkowski wrote:
Bingo. And furthermore, you should ALWAYS think before you write even one line of code.

Tip for you: The real problem here is not simply to find out if a number is prime - there are lots of ways to do it by brute force - it's to work out the correct steps for doing so.

So, assuming you're going to use a "progressive factor check" - and there's absolutely nothing wrong with that - a couple more questions for you, that may help you to get to the solution:
1. You now know that you shouldn't start at 1, because ALL numbers divide by 1; but where do you end? ie: what is the largest factor you need to check?
2. Do you think you need to check ALL factors in the range? For example: if I already know that my number n doesn't divide by either 2 or 3, is there any point in me checking if it divides by 6? And if not, which factors do you think make most sense to check?

HIH

Winston

Yes, I thought about what divisors to pick. I mean I only need one divisor besides 1 and the number x, and it means that x is composite, but I had some problems with small numbers such as 2 or 3 at first, so I thought that maybe it is more "safe" to divide by every number from [2;x) ( at first I tried [1;x] and I think that was my mistake).
What do you think about the code I posted a bit above, it does seem to work.

[Winston Gutkowski]

Akimbas Akimbasas wrote:What do you think about the code I posted a bit above, it does seem to work.

Yup. Looks like it to me too; but it's what I'd classify as a "brute force" check - ie, it does the job, but it contains a lot of checks that simply aren't required. And just to give you some idea how redundant it is: if you give it the number 971 (which is prime), it will spend around 98% of its time (and probably more) doing unnecessary work. But it will give you the correct answer.

So, if your only consideration is whether the program produces the correct result, then your job is done. However, if you'd like to try for the car, see if you can make it work a bit more efficiently.

I should add that this is one of the very few times that I would advise looking at efficiency.

In general, if you have a solution that is
(a) correct   and
(b) simple   (and your program qualifies on both counts)
then your job is done.

But in this case, prime number checking is a very useful generic tool, so if you can also make it as fast as possible, you'll have a very useful method you can stick in a utility class somewhere, for later use.

Winston

[Akimbas Akimbasas]

Winston Gutkowski wrote:
Yup. Looks like it to me too; but it's what I'd classify as a "brute force" check - ie, it does the job, but it contains a lot of checks that simply aren't required. And just to give you some idea how redundant it is: if you give it the number 971 (which is prime), it will spend around 98% of its time (and probably more) doing unnecessary work. But it will give you the correct answer.

So, if your only consideration is whether the program produces the correct result, then your job is done. However, if you'd like to try for the car, see if you can make it work a bit more efficiently.

I should add that this is one of the very few times that I would advise looking at efficiency.

In general, if you have a solution that is
(a) correct   and
(b) simple   (and your program qualifies on both counts)
then your job is done.

But in this case, prime number checking is a very useful generic tool, so if you can also make it as fast as possible, you'll have a very useful method you can stick in a utility class somewhere, for later use.

Winston

Thanks, since now I am a rookie, for a while I will only try to get the answer, once I get better at programming, I'll try pay to more attention to the efficiency of the program. I know that good program consists not only of a task getting done, but also about a task getting done fast.

[Winston Gutkowski]

Akimbas Akimbasas wrote:Thanks, since now I am a rookie, for a while I will only try to get the answer, once I get better at programming, I'll try pay to more attention to the efficiency of the program. I know that good program consists not only of a task getting done, but also about a task getting done fast.

Actually, I'd say that in general that's not quite right. A good program gets the job done correctly, but leaves scope for adding more stuff later on if it's needed - ie, it's designed on principles of code re-use.

Efficiency is almost always the last thing you want to worry about since, if you design your program correctly, the chances are that it will be fairly efficient anyway.

In your case, the problem actually asks two different (but related) questions:
1. Is n prime?
2. What are the factors of n?
and it may not be possible to get an optimal solution for both.

But working out the best answer to each one may get you close.

Winston