i wrote it today in C,compiled with tcc, figured out during preparation of compititive exams several years back. don't know if anyone already have wrote it alredy. it really fast(but you should decide whether it is fast or not). took one or two minuts to findout about 1,00,004 prime numbers between 10 and 1,00,00,000 on i7 processor with average 32% CPU use. as you know, only those can be prime which have last digit either 1,3,7 or 9 and to check if that number is prime or not, you have to divide that number by previously found prime numbers only. so first take group of four number = {1,3,7,9}, test it by dividing by known prime numbers, if reminder is non zero then number is prime, add it to prime number array. then add 10 to group so it becomes {11,13,17,19} and repeat the process.

#include <stdio.h>
int main() {    
    int nums[4]={1,3,7,9};
    int primes[100000];
    primes[0]=2;
    primes[1]=3;
    primes[2]=5;
    primes[3]=7;
    int found = 4;
    int got = 1;
    int m=0;
    int upto = 1000000;
    for(int i=0;i<upto;i++){
        //printf("iteration number: %d\n",i);
        for(int j=0;j<4;j++){
            m = nums[j]+10;
            //printf("m = %d\n",m);
            nums[j] = m;
            got = 1;
            for(int k=0;k<found;k++){
                //printf("testing with %d\n",primes[k]);
                if(m%primes[k]==0){
                    got = 0;
                    //printf("%d failed for %d\n",m,primes[k]);
                    break;
                }
            }
            if(got==1){
                //printf("got new prime: %d\n",m);
                primes[found]= m;
                found++;
            }
        }
    }
    printf("found total %d prime numbers between 1 and %d",found,upto*10);
    return 0;
}

I know it's somewhat later, but this could be useful to people arriving here from searches. Anyway, here's some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。

I found this solution pretty fast but it comes with consequences, So this is called Fermat's Little Theorem. If we take any number p and put that in (1^p)-1 or (2^p)-2...(n^p)-n likewise and the number we get is divisible by p then it's a prime number. Talking about consequences, it's not 100% right solution. There are some numbers like 341(not prime) it will pass the test with (2^341)-2 but fails on (3^341)-3, so it's called a composite number. We can have two or more checks to make sure they pass all of them. There is one more kind of number which are not prime but also pass all the test case:( 561, 1729 Ramanujan taxi no etc.

好消息是:在前250亿个数字中，只有2183不符合这个要求 的情况。

#include <iostream>
#include <math.h>
using namespace std;

int isPrime(int p)
{
    int tc = pow(2, p) - 2;
    if (tc % p == 0)
    {
        cout << p << "is Prime ";
    }
    else
    {
        cout << p << "is Not Prime";
    }
    return 0;
}

int main()
{
    int p;
    cin >> p;
    isPrime(p);
    return 0;
} 

如果它必须非常快，你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/

如果你只想知道某个数是不是质数，维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法，特别是因为它们可以告诉你一个数是否为质数。

#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}