2 qq 33748682 qq_33748682 于 2016.01.30 23:29 提问

C语言求素数算法,有几种方法可以降低时间复杂度

b可以非常大的时候,输出a到b之间素数的个数,怎么才能简化算法,降低运行时间

5个回答

caozhy
caozhy   Ds   Rxr 2016.01.30 23:48

采用列表法,每次找到新的素数,添加到表中。每次寻找素数,不用每个数字都尝试一次,而只要尝试小于这个数字的1/2的所有素数就可以了。

caozhy
caozhy   Ds   Rxr 2016.01.30 23:49
fz1989
fz1989   2016.01.31 09:58

不需要b的1/2,只需要判断到b的根号2

xianfajushi
xianfajushi   2016.01.31 10:44
cuiwei1026522829
cuiwei1026522829   Ds   Rxr 2016.01.31 19:48
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
降低时间复杂度的几种方法【持续更新】
降低时间复杂度的几种方法【持续更新】  LeetCode的许多题目都对时间复杂度有相应的要求,大家在刷题时遇到一道题可能有自己的解决方法,也确实可行,然而时间复杂度达不到要求也无法通过。这里给大家持续总结LeetCode中遇到的那些降低时间复杂度的方法。
求素数常用的几种方法
如何判断素数一个素是不是素数呢?或许你会以为这是一个非常简单问题,就像1+1=2一样,当一个数的因子只有1和它本身的时候就是素数,很简单的嘛!!!但是,当一个数特别大的时候就没有那么简单进行判断了。下面我们就求素数常用的一些方法进行讨论和判断。我们先来看看幼稚园的小孩子的做法:#include<stdio.h> #include<time.h> int IsPrime(in...
几种求素数与验证素数的方法
博主刚写了一篇Luogu T1125的解题报告,里面涉及到欧拉筛法。本篇博文会介绍一些素数筛法和素数验证法。 博主的数论并不是特别好,各路大神轻点喷 素数筛法1. Eratosthenes筛法又名:埃拉托斯特尼筛法 时间复杂度:O(nlog2log2n)O(nlog_{2}{log_{2}n}) 难度:☆具体代码:memset(check,false,sizeof(check)); i
求素数算法(C语言)
以下是用C语言求一定范围内的素数。#include<stdio.h> #include<math.h> int imax(int,int); void main(void) { int m,k,i; for(m=101;m<200;m+=2){ k=(int)sqrt((double) m); for(i=2;i<=k;i++){
C语言求素数的两种方法
1,判断n是否能被1~n-1整除 #include int main() { int i, n; scanf("%d", &n); for (i = 2; i < n ; i++) { if (n%i == 0) break; } if (i < n) printf("This is not a pr
求素数的几种高效方法
转贴文章请注明:逸学堂 求解一个算法,我们首先要知道它的数学含义.依据这个原则,首先我们要知道什么是素数.; 素数是这样的整数,它除了表示为它自己和1的乘积以外,无论他表示为任何两个整数的乘积。找素数的方法多种多样。1:是从2开始用“是则留下,不是则去掉”的方法把所有的数列出来(一直列到你不想再往下列为止,比方说,一直列到10,000)。第一个数是2,它是一个素数,所以应当把它留下来,然后继续往下
C语言求素数/质数最高效的方法
// 使用筛选法 #include #include int main(){          int count = 0;     int arr[101];// 定义一个数组将0-100之间的数依次作为数组元素存入数组中          for (int i = 0; i ; i++) {         arr
三种用C语言求素数的方法 筛选法..
素数 1.筛选法求1-100内的素数#include&amp;lt;stdio.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;#include&amp;lt;assert.h&amp;gt;//#include&quot;stdafx.h&quot;void Prime(int n){ int*arr=(int*)malloc(n*sizeof(int)); for(int i=0;i&amp;lt;n;i++) {  arr[i]=1...
素数判断的几种方法代码实现及其复杂度分析
素数判断的几种方法代码实现及其复杂度分析 <div class="article_manage clearfix"> <div class="article_l"> <span class="link_categories"> 标签: <a href="http://www.csd
几种常见排序算法的时间复杂度空间复杂度稳定性汇总表
 排序类别      时间复杂度    空间复杂度  稳定 1插入排序    O(n2)             1                   √ 2希尔排序   O(n2)              1                   × 3冒泡排序   O(n2)              1                   √ 4选择排序