vicky1997's blog

Implementation of finding the Prime Numbers upto a given number N .
By vicky1997, history, 8 years ago, In English

  • Hi all !!! *

  • Finding Prime Numbers In A Different Way... *

include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

int isprime(ll n)

{

if(n<=3)

    return 1;

if(n%2==0||n%3==0)

    return 0;

for(ll i=5;i*i<=n;i+=6)

{

    if(n%i==0||n%(i+2)==0)

        return 0;

}

return 1;

}

int main()

{

//ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

ll N,i;

cout<<"\nEnter the Number N :";cin>>N;

cout<<"\nPrime Numbers <="<<N<<" are : \n";

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

{

    if(isprime(i))

            {

        cout<<i<<",";

    }

}

return 0;

}

  • If found any corrections please comments... *

  • Help Appreciated... *

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int Size = 1e5+5;
    bool arr[Size];
    arr[1] = true;
    for(int i = 2; i <= sqrt(1e5); i++)
    {
        if(arr[i] == false)
        for(int j = i*i; j <= 1e5; j+= i)
            arr[j] = true;
    }

    //if arr[i] == false then i is a prime number
    return 0;
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You only need to change the constant 1e5 to the variable N whose value is input from cin or stdin.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is it efficient to answer all the queries where query<=1e6??????

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is classic fast implementation of simple check ,you can check . It is a fast ,but not very fast . If you want very very fast ,you must write sieve of eratosthenes.

My implementation of classic simple check .

long long checkprost(ll cis)
{
	if(cis==2 || cis==3)return 1;
	else if(cis==1 || cis%2==0 || cis%3==0)return 0;
	for(long long i=5,p=2;i*i<=cis;i+=p,p=6-p)
	{
		if(cis%i==0)return 0;
	}
	return 1;
}

If it is a simple ,it will return 1 ,else return 0 .

→ Reply