简单数论.pptx

上传人:99****p 文档编号:1514221 上传时间:2019-03-04 格式:PPTX 页数:28 大小:107.45KB
下载 相关 举报
简单数论.pptx_第1页
第1页 / 共28页
简单数论.pptx_第2页
第2页 / 共28页
简单数论.pptx_第3页
第3页 / 共28页
简单数论.pptx_第4页
第4页 / 共28页
简单数论.pptx_第5页
第5页 / 共28页
点击查看更多>>
资源描述

简单数论 李富数论l简而言之 ,数论是研究整数的理论l在 ACM竞赛中 ,经常用到数论的相关知识l纯 数论的题目不多 ,大部分是和其他类型的问题结合起来的l约数 ,倍数 ,模线性方程 ,欧拉定理 ,素数内容1.初等数论的概念2.求素数的方法3.最大公约数4.欧拉函数5.模线性方程6.中国剩余定理7.唯一 因子分解8.其他1.初等数论的概念整除性和约数:l假设 d和 a是整数, d|a(读作 d整除 a),意味着存在某个整数k,有 a=kd。l如果 d|a,并且 d0 ,则称 d是 a的约数。l每个整数 a都可以被其平凡约数 1和 a整除, a的非平凡约数也称为 a的因子 。1.初等数论的概念素数和合数l对于某个整数 a1,如果它仅有平凡约数 1和 a则称 p是素数。否则 p是合数。l可以证明素数有无限多个。l筛法求素数。1.初等数论的概念除法 定理 in;+i)for(j=0;jm +j)如果 pj整除 i,则 i不是素数如果都不能整除,则 i是素数,添加到素数列表 pN;缺陷:时间复杂度太高2.求素数的方法筛法求 1n所有素数l初始时容器内为 2到 n的所有 数l取出 最小的数 p,p一定是质数 ,删去 p的所有倍数 (注 :只需从 p2开始删除即可 )l重复 上述步骤直到容器为空l用 bool数组实现即可缺陷 :一个数可能被重复删去多次 ,影响效率

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。