算法模板——线性筛素数

实现功能:如题,筛出1——N内的所有素数

原理:如phile神犇所言,这次的才算是真正意义上的线性筛素数,其精髓在于if (i mod a[j])=0 then break;

因为——如果眼下的a[j]已经是i的因数了,则意味着即使再进行b[i*a[j]]:=1,那么I*b[j]也必然会被其他的数以同样的操作覆盖到,所以可以退出了,这个算法的思想在于减少重复劳动(鸣谢qcgrxx神犇,源链接

 1 var
 2    i,j,k,l,m,n:longint;
 3    a,b:array[0..1000000] of longint;
 4 begin
 5      readln(n);b[1]:=1;b[0]:=1;
 6      for i:=2 to n do
 7          begin
 8               if b[i]=0 then
 9                  begin
10                       inc(m);
11                       a[m]:=i;
12                  end;
13               for j:=1 to m do
14                   begin
15                        if a[j]>(n div i) then break;
16                        b[a[j]*i]:=1;
17                        if (i mod a[j])=0 then break;
18                   end;
19          end;
20      while true do
21            begin
22                 readln(m);
23                 writeln(b[m]=0);
24            end;
25 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杨建荣的学习笔记

通过shell脚本得到数据库的基本信息(一)(r9笔记第89天)

今天写了个脚本,虽然实现的功能不多,但是个人感觉是一个好的开始,架子出来了,后面要补充的细节加进来就逐步完善了。 这个脚本的运行效果如下: OS Ver...

3694
来自专栏Albert陈凯

2018-09-17 Vagrant 启动报错

Stderr: VBoxManage.exe: error: VT-x is disabled in the BIOS for all CPU modes (V...

4492
来自专栏Android小菜鸡

解决横竖屏切换导致自定义View切换Fragment失败

  自定义的BottomSelectView,在切换横竖屏后,底部选择器点击后Fragment不切换,失去效果。

1004
来自专栏SAP最佳业务实践

SAP S/4 HANA新变化-FI:GL总账

GENERAL LEDGER总账 General Ledger in S/4H is based in the Universal Journal; the l...

35210
来自专栏Java学习网

Java 语言版本整理,先到1.8版本,不全请补充

Java 语言版本 JDK 1.1.4 Sparkler 宝石 1997-09-12 JDK 1.1.5 Pumpkin 南瓜 1997-12-13 JDK 1...

2765
来自专栏IT笔记

SpringBoot开发案例之微信小程序录音上传

书接上回的《SpringBoot开发案例之微信小程序文件上传》,正常的业务流程是,口语测评需要学生通过前端微信小程序录入一段音频,通过调用第三方音频处理服务商进...

9528
来自专栏IT笔记

SpringBoot开发案例之微信小程序录音上传

前言 书接上回的《SpringBoot开发案例之微信小程序文件上传》,正常的业务流程是,口语测评需要学生通过前端微信小程序录入一段音频,通过调用第三方音频处理服...

1.4K8
来自专栏有趣的django

21天打造分布式爬虫-下载汽车之家图片(九)

1363
来自专栏白驹过隙

ACE - 代码层次及Socket封装

原文出自http://www.cnblogs.com/binchen-china,禁止转载。

861
来自专栏张善友的专栏

如何分析Performance Monitor (PerfMon) Log

  Windows 2003 和xp提供了性能监视器的几个命令行工具,他们是logman utility (logman.exe),relog utility ...

2118

扫码关注云+社区

领取腾讯云代金券