快速查找某个范围内的所有素数

观察以下素数表，不能被小于素数n的素数整除的最小数为下一个最小素数。换句话说所谓素数可以看做是坐标中不断使用更小素数的倍数填充后剩余的最小数。

例：

1】2是最小素数，使用2的倍数不断填充坐标后，未被填充的最小数就是3，于是3就是大于2的下一个素数

2】然后使用3的倍数不断填充坐标，剩余的未被填充的最小数就是5（4已经被2的倍数填充），可以发现5是大于3的下一个素数

3】依次类推可以顺序的求解所有素数

...

隐隐约约觉得，通过以上规律可以推出某范围内素数个数与素数值的关系，我自己就没有再推了，有兴趣的可以尝试一下，如果有结果了望能分享给我一下，感谢。

然后“talk is cheap，give me the code（废话少说，放码过来）”

clc
clear all
close all

numEnter = 100000;
numVector = zeros(1,numEnter);
numVector(1,1) = 1;
disp('2');
divNum = 2;
tempVector = find(~numVector);

tic
while(divNum <= numEnter)
    for iloop1 = 1:length(tempVector)
        % 小于divNum的数字不需要重复判断，相较于从2开始计算，可以节省1/3的时间（numEnter = 100000时）
        if(mod(tempVector(iloop1),divNum) == 0)
            numVector(1,tempVector(iloop1)) = 1;
        end
    end
    
    tempVector = find(~numVector);       % 寻找所有原始向量中的零元素坐标
    if (min(size(tempVector))>0)
        divNum = tempVector(1,1);           % 剩余的零元素的第一个坐标就是下一个素数
    else
        disp('end');
        break;
    end
    disp(divNum);
    % disp 命令会增加耗时5%左右
end
toc

以上代码的最大特点就是使用排除法对整个数列进行筛选，一旦某个数字被确定是非素数，该数字就会被排除在下一轮的判断之外，同时一旦被确定了这个数是素数，那么所有不大于这个数的数字都会被排除在下一轮的判断之外，运行耗时如下，这是当前已知在不对任何一个素数漏判的前提条件下所需计算量最小的算法。

Elapsed time is 3.513769 seconds.

扫描验证一下n = 10000以内范围中，素数个数与n/lnn之间的关系（扫描时候用倍频程，应该得到的曲线会更漂亮一些，而且需要的计算量会更少一些）。

clc
clear
close all

range = 1000;
range1 = zeros(1,range);
nlnnVector = zeros(1,range);
primeNumberAcountVector = zeros(1,range);
radioVector = zeros(1,range);

hbar = waitbar(0,'计算进度');
for iloop1 = 1:range
    range1(iloop1) = iloop1*10;
    nlnnVector(iloop1) = range1(iloop1)/log(range1(iloop1));
    
    primeNumberAcount = primeNumberSolute(range1(iloop1));
    primeNumberAcountVector(iloop1) = primeNumberAcount;
    
    radioVector(iloop1) = primeNumberAcountVector(iloop1)/nlnnVector(iloop1);
    
    waitbar(iloop1/range);
end
close(hbar)

figure
subplot(2,1,1)
hold on
plot(range1,nlnnVector)
plot(range1,primeNumberAcountVector);
legend('nlnnVector','primeNumberAcountVector')
hold off
subplot(2,1,2)
semilogx(range1,radioVector)

结果如下图

图2是两个结果之间的比值。