-





Prime Numbers


Prime number are the number which have only 2 divisor...1 and itself...
Example:
2 3 5 7 11 13 17 19 23 …..
Prime number have many application in computer science....ans also 
There are many methods to check weather a number is PRIME or not.
Example:
    • Fermat Method
    • Miller–Rabin
    • Solovay-Strassen
    • Lucas Primality Test


Different Algorithms to check the prime numbers:
  • Sieve of Eratosthenes
  • Segmented Sieve
  • Sieve of Sundaram
  • Bitwise Sieve
We will see each method and algorithm in different post.

In this Post we will discuss the basic method to test the number weather the number is Prime or not

Simple Approach:
        In this approach we will iterate over all the number from 1 to N-1 and check weather 
        that number divides the number or not....
        Here is simple CPP program for the above approach..

#include <bits/stdc++.h>
using namespace std;
  

bool isPrime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
  
    return true;
}
  
int main()
{
    int N=13;
bool flag=true;
if (N <= 1)
        flag= false;
else
{
    for (int i = 2; i < n; i++)
        if (n % i == 0) {
            flag false;
break;}
}

if(flag)
cout<<"YES";
else
cout<<"NO";
    return 0;
}



Time complexity :O(n)

This is the basic method to check the prime number ,in the next post we will see the seive algorithm to check the number in the range from L to R 
Here is an intresting application of prime number
https://letuscp.blogspot.com/2019/10/sphenic-number-sphenic-number-positive.html
  


Comments

Post a Comment

Popular posts from this blog

-
Image
Sphenic Number A  Sphenic Number  is a positive integer  n  which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather the first 3 digits after 1 are prime or not. Eg. 30 (sphenic number) 30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30) the set of divisor is (1,2,3,5,6,10,15,30) Examples: 30 = 2 × 3 × 5 Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather...
Read more

Fibonacci numbers with help of DP

-
Image
Well...the most and simple program which every programmer may have solved at least once.... Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.... with base condition f(0)=0  f(1)=1 In general: f(n)=f(n-1) +f(n-2) Basic Approach: A simple method that is a direct recursive implementation mathematical recurrence relation given above Here is simple CPP program.... #include<bits/stdc++.h> using namespace std;     int fib( int n) {      if (n <= 1)          return n;      return fib(n-1) + fib(n-2); }     int main () {      int n = 9;      cout << fib(n);      return 0; } That was simple....isn't it........
Read more
-
Image
Tutorial-2 is out!!!!! Fasten your seat-belt! Problem-2:- Understanding this problem and its solution properly will make a strong foundation for you in the DP world .(This worked for me :-) ) Here we go- Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:- Sum of those elements is maximum(Sum of the subset is maximum) . No 2 elements in the subset should be consecutive. Example :- {2,4,6,7,8} Answer:- {2+6+8=16} Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array. For the above example, dp[1] = 2 (2), [This is the best answer you could get if size of the array was one] dp[2]= 4(4),[This is the best answer you could get if size of the array was two] dp[3]=8(6+2),[This is the best answer you could get if size of the array was three]………lets call this equation-(1)… dp[4]=11(7+4),[This is the best answer you could get if size of ...
Read more