Check if Number is Prime or Composite

AIM

To write a Python program that checks whether a given number is a prime number or a composite number.

ALGORITHM

1. Start
2. Input a number from the user
3. Check if the number is 0 or 1 - if yes, print "neither prime nor composite"
4. If the number is greater than 1:
5. • Use a loop from 2 to n-1
   • Check if the number is divisible by any number in this range
   • If divisible, it's composite; otherwise, it's prime
6. If the number is negative, ask for a positive integer
7. Display the result
8. Stop

PROGRAM

# Python program to check if a number is prime or composite

n = int(input("Enter any number: "))

if (n == 0 or n == 1):
    print("Number is neither Prime nor Composite")
elif (n > 1):
    for i in range(2, n):
        if (n % i == 0):
            print("Number is not Prime but Composite")
            break
    else:
        print("Number is Prime number but not Composite")
else:
    print("Please enter positive integer number")

OUTPUT

CONCLUSION

Thus, the given program was successfully executed and the output was verified as per the expected result.

VIVA QUESTIONS

1. What is the difference between prime and composite numbers?

   Prime numbers have exactly two factors (1 and itself), while composite numbers have more than two factors. For example, 7 is prime (factors: 1, 7) and 12 is composite (factors: 1, 2, 3, 4, 6, 12).

2. Why are 0 and 1 neither prime nor composite?

   By definition, prime numbers must be greater than 1 and have exactly two distinct factors. 0 has infinite factors, and 1 has only one factor (itself), so neither fits the definition.

3. What is the purpose of the break statement in this program?

   The break statement exits the loop immediately when a divisor is found, making the program more efficient by avoiding unnecessary iterations.

4. How does the for-else construct work in Python?

   The else block executes only if the for loop completes normally (without encountering a break). If break is executed, the else block is skipped.

5. Can you optimize this algorithm for better performance?

   Yes, we can check divisors only up to √n instead of n-1, and check for even numbers separately to reduce iterations by half.

6. What happens if we input a very large prime number?

   The program will take longer to execute as it checks all numbers from 2 to n-1. For large numbers, more efficient algorithms like Miller-Rabin test are preferred.

7. Is 2 a prime number? Why is it special?

   Yes, 2 is prime and it's the only even prime number. All other even numbers are divisible by 2, making them composite.

8. How would you modify this program to find all prime numbers up to n?

   We would use nested loops or implement the Sieve of Eratosthenes algorithm to efficiently find all primes up to a given number.