【C# 每日一题6】素数个数

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Primes
{
   public class Primes
   {
      private long min;
      private long max;      public Primes()
         : this(2, 100)
      {
      }      public Primes(long minimum, long maximum)
      {
         if (min < 2)
            min = 2;
         else
            min = minimum;         max = maximum;
      }      public IEnumerator GetEnumerator()
      {
         for (long possiblePrime = min; possiblePrime <= max; possiblePrime++)
         {
            bool isPrime = true;
            for (long possibleFactor = 2; possibleFactor <=
               (long)Math.Floor(Math.Sqrt(possiblePrime)); possibleFactor++)
            {
               long remainderAfterDivision = possiblePrime % possibleFactor;
               if (remainderAfterDivision == 0)
               {
                  isPrime = false;
                  break;
               }
            }
            if (isPrime)
            {
               yield return possiblePrime;
            }
         }
      }
   }
}
   class Program
   {
      static void Main(string[] args)
      {
         Primes primesFrom2To1000 = new Primes(2, 1000);
         foreach (long i in primesFrom2To1000)
            Console.Write("{0} ", i);         Console.ReadKey();
      }
   }

用素数筛，复杂度是O(n)
#include <algorithm>
#include <cstdio>template<int MAX_PRIME>
struct PNMaker {
    bool isP[MAX_PRIME]; //标记某个数是不是素数
    int p[MAX_PRIME]; //素数线性表
    //找出[1, N)的所有素数,并且返回素数的个数
    inline int makePrimes(int N) {
        fill(isP, isP + N, true);
        int i, j;
        int top = 0;
        int x;
        isP[0] = isP[1] = false;
        for (i = 2; i < N; ++i) {
            if (isP[i]) p[top++] = i;
            for (j = 0; j < top; ++j) {
                x = p[j] * i;
                if (x >= N) break;
                isP[x] = false;
                if (i % p[j] == 0) break;
            }
        }
        return top;
    }
    /////////////////////////////////////    int p_num;
    void init() {
        p_num = makePrimes();
    }    int getNum() { return p_num;}
    bool isPrm(int i) { return isP[i]; }
    int get(int index) { return p[index]; }    /////////////////////////////////////    bool isPrmForce(unsigned int p) {
        if (p == 2 || p == 3) return true;
        else if(p % 2 == 0 || p % 3 == 0) return false;
        int step = 4;
        int i;
        for (i = 5; i * i <= p; i += step) {
            if (p % i == 0) return false;
            step = 6 - step;
        }
        return true;
    }
};using namespace std;
PNMaker<10000005> p;int main() {
    int a, b;
    scanf("%d %d", &a, &b);
p.makePrimes(b);
    int cnt = 0;
    for (int i = a + 1; i < b; ++i)
        if (p.isPrm(i))
            ++cnt;
    printf("%d\n", cnt);
return 0;
}

...改一下Main()不就行了,可以在控制台输入你的样例的.这点不用我再写了吧.

算法上做了改进，还有没有其他更好的方法了！
这个方法要是多个数据的话，也是很慢的！！
ACM上会Time Limited！！！

代码经过修改说明我的程序是可以连续测试样例的using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Primes
{
   public class Primes:IDisposable
   {
      private long min;
      private long max;      public Primes()
         : this(2, 100)
      {
      }      public Primes(long minimum, long maximum)
      {
         if (min < 2)
            min = 2;
         else
            min = minimum;         max = maximum;
      }      public IEnumerator GetEnumerator()
      {
         for (long possiblePrime = min; possiblePrime <= max; possiblePrime++)
         {
            bool isPrime = true;
            for (long possibleFactor = 2; possibleFactor <=
               (long)Math.Floor(Math.Sqrt(possiblePrime)); possibleFactor++)
            {
               long remainderAfterDivision = possiblePrime % possibleFactor;
               if (remainderAfterDivision == 0)
               {
                  isPrime = false;
                  break;
               }
            }
            if (isPrime)
            {
               yield return possiblePrime;
            }
         }
      }

           public void Dispose()
     {
        Dispose(true);
        GC.SuppressFinalize(this);
     }
     protected virtual void Dispose(bool disposing)
     {
        if (!m_disposed)
        {
            if (disposing)
            {
               // Release managed resources
            }

            // Release unmanaged resources
            m_disposed = true;
        }
     }
     ~Primes()
     {
        Dispose(false);
     }
     private bool m_disposed;
   }
}
   class Program
   {
      static void Main(string[] args)
      {
          string s ="";
          while(!(s.ToLower().Equals("exit")))
          {
              Console.WriteLine("请输入你要输出素数的范围如1000");
              long i = long.Parse(Console.ReadLine());
              using(Primes primesFrom2To1000 = new Primes(2 , i))
              {
                  foreach(long j in primesFrom2To1000)
                      Console.Write("{0} " , j);
              }
              Console.WriteLine();
              Console.WriteLine("请输入exit退出或者继续");
              s = Console.ReadLine();

          }
      }
   }

这个版本无论你有多少行询问复杂度都是O(N + M)，N是被询问里最大的那个数（<10000000), M是询问的个数
#include <algorithm>
#include <cstdio>
using namespace std;template<int MAX_PRIME>
struct PNMaker {
    bool isP[MAX_PRIME]; //标记某个数是不是素数
    int p[MAX_PRIME]; //素数线性表
    //找出[1, N)的所有素数,并且返回素数的个数
    inline int makePrimes(int N) {
        fill(isP, isP + N, true);
        int i, j;
        int top = 0;
        int x;
        isP[0] = isP[1] = false;
        for (i = 2; i < N; ++i) {
            if (isP[i]) p[top++] = i;
            for (j = 0; j < top; ++j) {
                x = p[j] * i;
                if (x >= N) break;
                isP[x] = false;
                if (i % p[j] == 0) break;
            }
        }
        return top;
    }
    /////////////////////////////////////    int p_num;
    void init() {
        p_num = makePrimes();
    }    int getNum() { return p_num;}
    bool isPrm(int i) { return isP[i]; }
    int get(int index) { return p[index]; }
};
struct duo {
    int a, b;
    void set(int x, int y) { a = x; b = y; }
};////////////////////////////////////////////////////////////
PNMaker<10000005> p;
int before[10000005];duo query[1000000];
int maxNum;
int N;//////////////////////////////////////////////////////////////
void input() {
    int i = 0;
    int a, b;
    maxNum = -99999999;
    while(1) {
        if (scanf("%d %d", &a, &b) == 2) {
            query[i].set(a, b);
            ++i;
            maxNum = max(maxNum, max(a, b));
        }
        else
            break;
    }    N = i;
}
void init() {    p.makePrimes(maxNum+1);
    before[2] = 0;
    for (int i = 3; i <= maxNum; ++i) {        before[i] = before[i-1] + (p.isPrm(i-1) ? 1 : 0);
    }
}
void run() {
    int i;
    for (i = 0; i < N; ++i) {
        int a, b;
        a = query[i].a;
        b = query[i].b;
        printf("%d\n", before[b] - before[a] - (p.isPrm(a) ? 1 : 0));
    }}int main() {    input();
    init();
    run();
return 0;
}

其实用线性素数筛子绝对可以解决了，因为可以利用预处理来应付多个数据的问题先用素数筛子把1..N以内的素数全部选出来，这个复杂度是O(N)
然后令B[i] 表示 [1..i) 区间内的素数个数，我们有B[i] = B[i-1] + （i-1是素数 ? 1 : 0）,这一步的复杂度也是O(N)
然后对于每个询问(a,b)，只要输出 B[b] - B[a] - (a是素数 ? 1 : 0)，这一步的复杂度是O(M),因为总共有M个询问所以最后的复杂度O(N+M)

来个急速版的        static void Main()
        {
            Console.WriteLine((int)PrimeCount(1000000));
            Console.Read();
        }
        static double PrimeCount(double num)
        {
            return num / Math.Log(num);
        }太快了，所以会有误差~~~~~~~

这是带注释的版本：#include <algorithm>
#include <cstdio>
using namespace std;template<int MAX_PRIME>
struct PNMaker {
    bool isP[MAX_PRIME]; //标记某个数是不是素数
    int p[MAX_PRIME]; //素数线性表
    //找出[1, N)的所有素数,并且返回素数的个数
    inline int makePrimes(int N) {
        fill(isP, isP + N, true);
        int i, j;
        int top = 0;
        int x;
        isP[0] = isP[1] = false;
        for (i = 2; i < N; ++i) {
            if (isP[i]) p[top++] = i;
            for (j = 0; j < top; ++j) {
                x = p[j] * i;
                if (x >= N) break;
                isP[x] = false;
                if (i % p[j] == 0) break;
            }
        }
        return top;
    }
    /////////////////////////////////////    int p_num;
    void init() {
        p_num = makePrimes();
    }    int getNum() { return p_num;}
    bool isPrm(int i) { return isP[i]; }
    int get(int index) { return p[index]; }
};
struct duo {
    int a, b;
    void set(int x, int y) { a = x; b = y; }
};////////////////////////////////////////////////////////////
PNMaker<10000005> p;
int before[10000005];duo query[1000000];
int maxNum;
int N;//////////////////////////////////////////////////////////////
void input() {
    int i = 0;
    int a, b;
    maxNum = -99999999;
    while(1) {
        if (scanf("%d %d", &a, &b) == 2) {
            query[i].set(a, b);  //把询问存起来！
            ++i;
            maxNum = max(maxNum, max(a, b)); //maxNum表示所有的询问(a,b)里的最大的a或者b
        }
        else
            break;
    }    N = i;
}
void init() {    p.makePrimes(maxNum+1);  //进行素数筛子的工作，这一步结束以后就可以在O(1)内判断某个数是不是素数了！
    before[0] = 0;
    before[1] = 0;
    before[2] = 0; //before[i] 表示在[1,i)内的素数的个数
    for (int i = 3; i <= maxNum; ++i) {
        before[i] = before[i-1] + (p.isPrm(i-1) ? 1 : 0); //递推每个before[i]
    }
}
void run() {
    int i;
    for (i = 0; i < N; ++i) {
        int a, b;
        a = query[i].a;
        b = query[i].b;
        printf("%d\n", before[b] - before[a] - (p.isPrm(a) ? 1 : 0)); //每个询问都可以在O(1)解决
    }}int main() {    input();
    init();
    run();
return 0;
}

    static class Solver
    {
        const int MaxLength = 10000000;
        static int[] masks = new int[MaxLength];
        static Solver()
        {
            for(int i = 2; i<MaxLength; i++)
            {
                if (masks[i] != 0)
                {
                    masks[i] = masks[i - 1];
                }
                else
                {
                    masks[i] = masks[i - 1] + 1;
                    for (int elimiate = i + i; elimiate < MaxLength; elimiate += i)
                    {
                        masks[elimiate] = -1;
                    }
                }
            }
        }        public static int CountPrimes(int floorExclusive, int ceilingExclusive)
        {
            if (ceilingExclusive <= floorExclusive) return 0;
            return masks[ceilingExclusive - 1] - masks[floorExclusive];
        }
    }

这个方法和我的方法用的是同一种加速的原理，只不过他是在筛子里给B[i]赋值，我那个也可以改成在筛子内给B[i]，但是复杂度不会降低

用Meissel-Lehmer method，可以更快，低于线性的，有功夫写一个。

用hashmap记录素数和其对应在[1,10000000]素数队列的下标，然后直接去查hashmap即可。
hashmap效率很高的。
下面是java code
package com.myprime;import java.util.HashMap;public class MyPrimes {
private int low;
private int high; private final int MIN = 1;
private final int MAX = 10000000;
private static HashMap<Integer, Integer> primesHashMap = new HashMap<Integer, Integer>();//key = 素数，value = 素数所在的素数队列中的下标
private static boolean isFirst = true;//如果是第一次测试，就将该区间所有素数放到map里

public MyPrimes(int low,int high){
this.low = low;
this.high = high;
}

public int getLow() {
return low;
} public int getHigh() {
return high;
} public int getNum(){
System.out.println("low = " + low + " high = " + high);
int lownum = 0,highnum = 0;
//仅在第一次的时候查找
if(isFirst == true){
getPrimes();
}
lownum = getLowPrime();
//该范围内没有素数
if(lownum == 0){
return 0;
}
highnum = getHighPrime();
//不要忘记+1
return primesHashMap.get(highnum) - primesHashMap.get(lownum) + 1;
}

//获取离low最近的素数
private int getLowPrime(){
for(int i = getLow();i <= getHigh();i++){
if(isPrime(i) == true){
return i;
}
}
return 0;
}

//获取离high最近的素数
private int getHighPrime(){
for(int i = getHigh();i >= getLow();i--){
if(isPrime(i) == true){
return i;
}
}
return 0;
}

private void getPrimes(){
int index = 1;
for(int i = MIN;i <= MAX;i++){
if(isPrime(i) == true){
primesHashMap.put(i, index++);
}
}
isFirst = false;
}

private boolean isPrime(int n){
if(n == 1){
return false;
}
for(int i = 2;i <= Math.sqrt(n);i++){
if(n % i == 0){
return false;
}
}
return true;
}
}
package com.myprime;public class MainTest { public static void main(String[] args) {
System.out.println(new MyPrimes(12345, 987654).getNum());
System.out.println(new MyPrimes(1, 12).getNum());
System.out.println(new MyPrimes(10, 10).getNum());
System.out.println(new MyPrimes(666, 7777).getNum()); }}
result:
low = 12345 high = 987654
count = 76140
low = 1 high = 12
count = 5
low = 10 high = 10
count = 0
low = 666 high = 7777
count = 864

题目漏看了句话求a b之间（不算a,b）的素数个数！。。
//获取离low最近的素数
private int getLowPrime(){
for(int i = getLow();i <= getHigh();i++){//改成 getLow() + 1
if(isPrime(i) == true){
return i;
}
}
return 0;
}//获取离high最近的素数
private int getHighPrime(){
for(int i = getHigh();i >= getLow();i--){ //改成 getHigh() - 1
if(isPrime(i) == true){
return i;
}
}
return 0;
}哈哈，又犯小错误了～～

本人解法：根据初等数论，不能被其平方根之内的数整除就不是素数。http://blog.csdn.net/xiaoxin888888/archive/2011/05/27/6450182.aspx

贴一个网上参考的算法
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static public void priem(int size)
        {
            int n = 0;
            if (size % 2 == 0)
                n = (size - 2) / 2;
            else
                n = (size - 1) / 2;
            bool[] p = new bool[n];
            for (int i = 0; i < n; i++)
                p[i] = true;// 初始化全部奇数为素数。p[0]对应3，即p[i]对应2*i+3
            for (int i = 0; i < Math.Sqrt(size); i++)
            {
                if (p[i])//如果 i+i+3 是素数
                {
                    for (int k = i + i + 3, j = k * i + k + i; j < n; j += k) // 筛法起点是 p[i]所对应素数的平方 k^2
                        // k^2在 p 中的位置是 k*i+k+i
                        //    下标 i         k*i+k+i
                        //对应数值 k=i+i+3   k^2
                        p[j] = false;
                }
            }
            Console.WriteLine(2);
            for (int i = 0; i < p.Length; i++)
            {
                if (p[i])
                {
                    Console.WriteLine(3 + 2 * i);
                }
            }
            Console.Read();
        }        static void Main(string[] args)
        {
            priem(100);
        }
    }
}

        //素数的个数
         public static int CountPrimes(int min, int max)
        {
            int count = 0;
            for (int i = min+1; i < max; i++)
            {
                if (IsPrime(i))
                    count++;
            }
            return count;
        }
        //判断是否是素数
         public static bool IsPrime(int n)
        {
            bool flag=false;
            for (int i = 2; i < n; i++)
            {
                flag = n % i == 0;
                if (flag)
                    break;
            }
            return !flag;
        }

贴个最简单的，也是最费时间的~~~~~~
其实，最快的就是用已经建立好的素数表进行直接查找~~~~~
找素数真的是门高深的学问~~~
#include <iostream>
using namespace std;
int main()
{
bool isPrime(const int);
int low, high;
cin >> low >> high;
for(int i = low; i <= high; ++i)
if(isPrime(i))
cout << i << "\t";
cout << endl;
return EXIT_SUCCESS;
}bool isPrime(const int value)
{
int temp = value;

for(int i = 2; i < value; ++i)
{
if(0 == temp % i)
return false;
}
return true;
}

class Program
{    const int N = 10000000;
    static int[] nums = new int[(N >> 5) + 1];
    static void Main(string[] args)
    {
        CreatePrimeTable();
        Console.WriteLine(PrimeCount(8000, 10000));
        Console.WriteLine(PrimeCount(10, 10000000));
        Console.Read();
    }
    //用筛法获得素数表。
    //Convert.ToString(nums[0],2)得到的字符串1011111011101011101011101010011表示0-31的素数情况
    //从左到右，0表示素数 1表示合数
    //依次类推nums[1] 表示32-63 的素数表
    private static void CreatePrimeTable()
    {
        nums[0] = 3;
        for (int i = 2; i <= N; i++)
            if ((nums[i >> 5] & (1 << (i & 31))) == 0)
                for (int x = i + i; x <= N; x += i)
                    nums[x >> 5] |= (1 << (x & 31));
    }    //从素数表查询素数的个数。
    private static int PrimeCount(int startNum, int endNum)
    {
        startNum++;//因为不算自身
        endNum--; //因为不算自身
        if (startNum < 0 || endNum > N || startNum > endNum) return 0;
        int s1, s2, e1, e2, count = 0;
        s1 = startNum >> 5;
        e1 = endNum >> 5;
        s2 = startNum & 31;
        e2 = endNum & 31;
        if (s1 == e1)
            return ZeroCount(nums[s1], s2, e2);
        count += ZeroCount(nums[s1], s2, 31);
        for (int i = s1 + 1; i < e1; i++)
            count += ZeroCount(nums[i], 0, 31);
        count += ZeroCount(nums[e1], 0, e2);
        return count;
    }    //单个素数表num中0(素数)的个数
    //startBit查询的开始位，左边界 endBit查询的结束位右边界
    private static int ZeroCount(int num, int startBit, int endBit)
    {
        uint maskNum = uint.MaxValue;
        maskNum <<= 31 - endBit;
        maskNum >>= 31 - endBit + startBit;
        maskNum <<= startBit;
        maskNum = (uint)(num & maskNum);
        int count = 0;
        while (maskNum > 0)
        {//2进制数中1的个数。
            count ++;
            maskNum &= (maskNum - 1);
        }
        return endBit- startBit + 1 - count;//总查询数 - 1的个数 = 0的个数
    }

跟我在大一写的差不多：
static void Main(string[] args)
{
Console.WriteLine("请输入你要计算的从2到多少的素数：");
            int N = Convert.ToInt16(Console.ReadLine());
            //const int N = 100;           //const指定N为常数，不能被修改
            bool[] isprime = new bool[N + 1];     //定义数组isprime为bool类型            int i, total = 0;
            for (i = 2; i < isprime.Length; i++)
            {
                isprime[i] = true;
            }
            for (i = 0; i < Math.Sqrt(N); i++)
            {
                if (isprime[i] == true)
                {

                        for (int k = 2 * i; k < isprime.Length; k = k + i)
                        isprime[k] = false;
                }
            }
            for (i = 2; i < isprime.Length; i++)
            {
                if (isprime[i] == true)
                {
                    total++;
                    Console.Write("{0,5}", i);
                    if (total % 10 == 0)
                        Console.WriteLine("\n");
                }            }
            Console.WriteLine("\n从2到{0}共有{1}个素数", N,total);
            Console.ReadKey();
        }

64楼代码，有一个地方忘记优化了
for (int i = 2; i <= N; i++)
可以改成
for (int i = 2; i <= Math.Sqrt(N); i++)

个人感觉算法不必写的那么详细,说一下我个人的思想吧.
首先不知楼主知不知道筛选素数的方法,比如10000以内的素数求法是-->一开始在H[10001]中去掉2的倍数-->循环到3,由于没有被去掉,去掉3的倍数,--->4(被去),5(没去,循环去掉5的倍数),6(去掉了),一直判断到根号10000 也就是100;
在此基础之上,将去掉的位置设置为0,没去掉的位置上保存一个递增的数值,比如2的时候是1,3的时候是2,5的时候是3;
例如
memset(H,1,10000);
int primeNum=1;
for(i=2;i<100;i++)
if(H[i]!=0){
    primeNum++;
    H[i]=primeNum;
    for(j=i*2;j<10000;j+=i)
    {
        H[j]=0;
    }
}
这样就构造好了一个素素个数的表.
在取得 n,m间的素数个数时.可以从n向前判断H[n-i]是否为0,用H[m-j]-H[n-i]"这里两个数都是m和n向前第一次遇到的非零值.",即为楼主想要的数字.
不知楼主能否明白我说的原理.
这个的第一个素数筛选方法是由素数的定义得到的只被1和自身整除,那么从2开始不断的去倍数,就排除了非素数. 而为什么是根号,可以用一个计算式说明 10*10=100 2*50=100 50*2=100,在根号左右的两个因子只是换了位置而已.
话就到此了.

这里一开始的primeNum应该置为0;
疏忽了.

求 PI(x) 有 O(N^(2/3+ε)) 的算法, 试过求 PI( 1E10 ) 也是秒出...

求思想，求代码，求验证！
求回答，是否是和31楼liyaoye的想法一样的！

public static void 高手()

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define XPREVN (64*1024*1024) /**/
#define XSQRTPREVN (8*1024)
#define XPREVPI (4*1024*1024) /* PI(XPREVN) : 3957809 */int *X_small_prime ,  X_pi_small_prime;
int *X_pi_prev_N   , *X_prev_V;#define XPREVDM (7)
#define XPREVQ (2*3*5*7*11*13*17)
#define XPREVPHQ (1*2*4*6*10*12*16)#ifdef _MSC_VER
typedef __int64 LLong;
#define LLFmt "I64d"
#else
typedef long long LLong;
#define LLFmt "Ld"
#endifstatic LLong phiX_p( LLong x , LLong a )
{
if( a == XPREVDM )
return x / XPREVQ * XPREVPHQ + X_prev_V[ x % XPREVQ ];
if( x < X_small_prime[a-1] )
return 1;
return phiX_p( x , a - 1 ) - phiX_p( x / X_small_prime[a-1] , a - 1 );
}LLong phiX( LLong X )
{
LLong cubeRootX  , max , len3 , len2 , s , i , k;
LLong sum , p;
if( X <= XPREVN )
return X_pi_prev_N[X];

max   = (LLong)(pow( (double)X , 2./3 ) + 2);
cubeRootX = (LLong)(pow( (double)X , 1./3 ) + .5);
if( cubeRootX*cubeRootX*cubeRootX > X )
--cubeRootX;
len3 = X_pi_prev_N[cubeRootX];

sum = 0; s = 0; k = max -1 ;
for( i = len3; ;++i )
{
p = X_small_prime[i];
if( p * p > X ) break;

s += X_pi_prev_N[k] - X_pi_prev_N[(int)((double)X/p)];
k = (int)((double)X/p);

sum += s;
}
len2 = X_pi_prev_N[p-1];

sum = (len2-len3)*X_pi_prev_N[max-1] - sum;
sum = len3 * (len3-1)/2 - len2 * (len2-1) / 2 + sum;

return phiX_p( X , len3 ) - sum + len3 - 1;
}void initSmallPrime()
{
char * = (char*)calloc(1,XPREVN/2+1);
int i , j;
X_small_prime = (int*)calloc(sizeof(int),XPREVPI );
X_pi_prev_N   = (int*)calloc(sizeof(int),XPREVN+1);
X_prev_V   = (int*)calloc(sizeof(int),XPREVQ+1);

for( i = 3; i <= XSQRTPREVN; i += 2 )
{
if( [i/2] ) continue;
for( j = i*i/2; j <= XPREVN/2; j+=i )
[j] = 1;
}
X_small_prime[0] = 2;
X_pi_small_prime = 1;
X_pi_prev_N[0] = X_pi_prev_N[1] = 0;
X_pi_prev_N[2] = 1;
for( i = 3; i <= XPREVN; i += 2 )
{
if( [i/2] )
{
X_pi_prev_N[i+1] = X_pi_prev_N[i] = X_pi_prev_N[i-1];
}
else
{
X_pi_prev_N[i+1] = X_pi_prev_N[i] = 1 + X_pi_prev_N[i-1];
X_small_prime[X_pi_small_prime++] = i;
}
}
free();

for( i = 0; i < XPREVQ; ++i )
X_prev_V[i] = i;
for( i = 1; i <= XPREVDM; ++i )
for( j = XPREVQ-1; j >= 0; --j )
X_prev_V[j] -= X_prev_V[ j/X_small_prime[i-1] ];
}int main()
{
LLong a , b;
initSmallPrime(); while( 2 == scanf( "%" LLFmt "%" LLFmt , &a , &b ) )
{
++a; --b;
if( a <= 0 || b <= 0 || a > b || b >= 100 * ((LLong)1 << 30) )
break; printf( "%" LLFmt "\n" , phiX( b ) - phiX( a ) );
}

return 0;
}

不会 C# , 只好贴个C的, 我这运行结果是:
$ cl -nologo -O2 -Ox -Og 1.c ; time ( echo 0 100000000000 | ./1 ) ; time ( echo 0 10000000000 | ./1 )
1.c
4118054813real    0m8.812s
user    0m0.046s
sys     0m0.000s
455052511real    0m1.640s
user    0m0.030s
sys     0m0.030s

struct PNMaker {
    bool isP[MAX_PRIME]; //标记某个数是不是素数
    int p[MAX_PRIME]; //素数线性表
    //找出[1, N)的所有素数,并且返回素数的个数
    inline int makePrimes(int N) {
        fill(isP, isP + N, true);
        int i, j;
        int top = 0;
        int x;
        isP[0] = isP[1] = false;
        for (i = 2; i < N; ++i) {
            if (isP[i]) p[top++] = i;
            for (j = 0; j < top; ++j) {
                x = p[j] * i;
                if (x >= N) break;
                isP[x] = false;
                if (i % p[j] == 0) break;
            }
        }
        return top;
    }

刚试了下时间，初始化素数表300ms  后面的运算不怎么用时间
class Program
{
    const int N = 10000000;
    static int[] nums = new int[(N >> 5) + 1];
    static void Main(string[] args)
    {
        DateTime dt = DateTime.Now;
        CreatePrimeTable();
        Console.WriteLine( "初始化时间:"+(DateTime.Now - dt).TotalMilliseconds);

        dt = DateTime.Now;
        Console.WriteLine("结果:" + PrimeCount(12345, 987654));
        Console.WriteLine("结果:" + PrimeCount(10, 10000000));
        Console.WriteLine("结果:" + PrimeCount(1, 100));        Console.WriteLine("运算时间:" + (DateTime.Now - dt).TotalMilliseconds);
        Console.Read();
    }
    //用筛法获得素数表。
    //Convert.ToString(nums[0],2)得到的字符串1011111011101011101011101010011表示0-31的素数情况
    //从左到右，0表示素数 1表示合数
    //依次类推nums[1] 表示32-63 的素数表
    private static void CreatePrimeTable()
    {
        nums[0] = 3;
        for (int i = 2; i <= Math.Sqrt(N); i++)
            if ((nums[i >> 5] & (1 << (i & 31))) == 0)
                for (int x = i + i; x <= N; x += i)
                    nums[x >> 5] |= (1 << (x & 31));
    }    //从素数表查询素数的个数。
    private static int PrimeCount(int startNum, int endNum)
    {
        startNum++;//因为不算自身
        endNum--; //因为不算自身
        if (startNum < 0 || endNum > N || startNum > endNum) return 0;
        int s1, s2, e1, e2, count = 0;
        s1 = startNum >> 5;
        e1 = endNum >> 5;
        s2 = startNum & 31;
        e2 = endNum & 31;
        if (s1 == e1)
            return ZeroCount(nums[s1], s2, e2);
        count += ZeroCount(nums[s1], s2, 31);
        for (int i = s1 + 1; i < e1; i++)
            count += ZeroCount(nums[i], 0, 31);
        count += ZeroCount(nums[e1], 0, e2);
        return count;
    }    //单个素数表num中0(素数)的个数
    //startBit查询的开始位，左边界 endBit查询的结束位右边界
    private static int ZeroCount(int num, int startBit, int endBit)
    {
        uint maskNum = uint.MaxValue;
        maskNum <<= 31 - endBit;
        maskNum >>= 31 - endBit + startBit;
        maskNum <<= startBit;
        maskNum = (uint)(num & maskNum);
        int count = 0;
        while (maskNum > 0)
        {//2进制数中1的个数。
            count ++;
            maskNum &= (maskNum - 1);
        }
        return endBit- startBit + 1 - count;//总查询数 - 1的个数 = 0的个数
    }
}

i = from min to max
j = from 2 to i.sqrt()
if i%10 != even && i%10 !=5
// 1 3 7 9
than the second floor

//可以输出除了2到10所有的，时间也可以。之于2到10，完全可以加个判断using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;namespace ConsoleApplication2
{
        class Program
        {
                static void Main(string[] args)
                {
                        long min = 10;
                        long max = 50;
                        NeedPrime first = new NeedPrime(min, max);
                        foreach (long i in first)
                        {
                                Console.WriteLine(i);
                        }
                        Console.Read();
                }
        }        class NeedPrime
        {
                private long min = 2;
                private long max = 100;                public NeedPrime(long min, long max)
                {
                        this.min = min;
                        this.max = max;
                }
                public IEnumerator GetEnumerator()
                {
                        for (long item = min; item < max; item++)
                        {
                                long ok = item % 10;
                        //        Console.WriteLine("tiaoshi:" + ok);
                                if (ok % 2 != 0 && ok % 5 != 0)
                                {
                                        bool isPrime = false;
                                        for (long tmp = 2; tmp <= (long)Math.Floor(Math.Sqrt(item)); tmp++)
                                        {
                        //                        Console.WriteLine("tmp= " + tmp);
                                                if (item % tmp == 0)
                                                {
                                                        isPrime = false;
                                                        break;
                                                }
                                                else
                                                {
                                                        isPrime = true;
                                                }
                                        }
                                        if (isPrime)
                                        {
                                                yield return item;
                                        }                                }
                        }
                }
        }
}

调试易

【C# 每日一题6】素数个数

解决方案 »