Program to check Prime number or not

PRIME NUMBER:

A prime number is a positive integer that is divisible only by itself and 1. In other words, it is a number that is not divisible by any other number except for 1 and itself. For example, 2, 3, 5, 7, 11, and 13 are all prime numbers.


PROGRAM (METHOD 1):

 #include <stdio.h>

int main()

{

    int i,n,flag=0;

    printf("Enter a number:");

    scanf("%d",&n);

    for(i=2;i<n;i++)

    if(n%i==0)

    flag++;

    if(flag==0)

    printf("%d is a prime number",n);

    else

    printf("%d is not a prime number",n);

    return 0;

}


TIME COMPLEXITY:

The time complexity is O(n) because the for loop iterates from 2 to n-1, and the number of iterations grows linearly with the input size n.


SPACE COMPLEXITY:

The program uses a constant amount of extra space to store the variables i and n, which doesn't depend on the size of the input. Therefore, the space complexity is O(1), indicating a constant amount of extra space used.


Positive test case


Negative test case



 

PROGRAM (METHOD 2):

In this method, we optimize the loop by only checking up to n/2. This is a common technique to reduce the number of iterations when checking for divisibility or primality.


#include <stdio.h> 

int main() 

{ 

    int n, flag = 1; 

    printf("Enter a number:"); 

    scanf("%d",&n); 

    for (int i = 2; i <= n / 2; i++) 

    { 

        if (n % i == 0) 

        { 

           flag = 0; 

            break; 

        }
    } 

    if (flag) {

      printf("The number %d is a Prime Number\n", n);
       

    } 

    else { 

        printf("The number %d is not a Prime Number\n", n);
    

    } 

    return 0; 


}



TIME COMPLEXITY:

The time complexity is O(n/2), which simplifies to O(n) since constant factors are ignored in Big O notation. The loop runs from 2 to n/2, which is half the range of the original loop, but it's still proportional to n.


SPACE COMPLEXITY:

The space complexity is O(1) because the program uses a fixed amount of extra space to store the variables, regardless of the input size.







PROGRAM (METHOD 3):

In this method, we can reduce the numbers to be checked from (N/2) to sqrt(N) making it much more efficient than the simple method.

The reason this works is that if N has a factor larger than its square root, it must also have a corresponding factor smaller than its square root. So, checking up to the square root is sufficient to determine if N is prime or not.


#include <math.h>  

#include <stdio.h>  

int main()  

{  

    int n, flag = 1; 

    printf("Enter a number:"); 

    scanf("%d",&n); 

    double sqroot = sqrt(n); 

    for (int i = 2; i <= sqroot; i++) 

    { 

        if (n % i == 0) { 

            flag = 0; 

            break;
        } 

    } 

    if (flag) { 

        printf("%d is a prime number", n); 

    } 

    else { 

        printf("%d is not a prime number", n); 

    } 

    return 0; 

}


TIME COMPLEXITY:

The time complexity is O(sqrt(n)) as the loop only runs up to the square root of the input number.

SPACE COMPLEXITY:

The space complexity is O(1) because the program uses a fixed amount of extra space, regardless of the input size. 








Comments

Post a Comment

Popular posts from this blog

Swap two numbers without using third variable

Image
SWAPPING TWO NUMBERS WITHOUT USING A THIRD VARIABLE There are two common ways to swap two numbers without using a third variable: PROGRAM 1 (Using addition and Subtraction): #include <stdio.h> int main() {     int a,b;     printf("enter the value of a: ");     scanf("%d",&a);     printf("enter the value of b: ");     scanf("%d",&b);     printf("Before swapping, a=%d b=%d.",a,b);     a=a+b;     b=a-b;     a=a-b;     printf("\nAfter swapping, a=%d b=%d.",a,b);     return 0; } PROGRAM 2 (Using Bitwise XOR): #include <stdio.h> int main() {     int a,b;     printf("enter the value of a: ");     scanf("%d",&a);     printf("enter the value of b: ");     scanf("%d",&b);     printf("Before swapping, a=%d b=%d.",a,b);     a=a^b;     b=a^b;     a=a^b;     printf("...
Read more

Program to check leap year

Image
LEAP YEAR: A leap year is a year that is divisible by 4, but not by 100, unless it is also divisible by 400. This means that years like 2024, 2020, and 2016 are leap years, but 2100 is not. PROGRAM: include <stdio.h> int  main() {     int year;     printf("Enter the year: ");     scanf("%d",&year);     if((year%4==0 && year%100!=0) || year%400==0)     {     printf("%d is a leap year", year);     }     else     {     printf("%d is not a leap year", year);     }     return 0; } TIME COMPLEXITY: The time complexity of this program is O(1) because the program only performs a fixed number of operations regardless of the input size. The if- else statement and the printf statements are executed once each, making the time complexity O(1). SPACE COMPLEXITY: The space complexity is O(1) because the program only uses a constant amount of memory to stor...
Read more

Check a number is palindrome or not

Image
PALINDROME: A palindrome is a word, phrase, or sequence that reads the same backward as forward.  A number palindrome is a numerical palindrome, where the digits read the same when reversed. For example, 12321 is a palindrome whereas 12345 is not a palindrome. PROGRAM: #include <stdio.h> int main() {     int n,m,rem,rev=0;     printf("Enter any number: ");     scanf("%d",&n);     m=n;     while(n!=0)     {         rem=n%10;         rev=rev*10+rem;         n=n/10;     }     if(rev == m)     printf("%d is a palindrome", m);     else     printf("%d is not a palindrome",m);     return 0; } TIME COMPLEXITY: The time complexity of the program is indeed O(log n) because the number of iterations in the while loop is proportional to the number of digits in the input number 'n'. As the number of digits in...
Read more