精华内容
下载资源
问答
  • 2021-05-21 16:25:48

    import java.io.BufferedReader;

    import java.io.IOException;

    import java.io.InputStreamReader;

    /**

    * @author 枳洛淮南

    * @version 1.0

    * @Description 功能

    * @Date 2021/3/30 下午 18:57

    */

    public class Main

    {

    //用筛选法求n以内的素数。筛选法求解过程为:将2~n之间的正整数放在数组内存储,

    // 将数组中2之后的所有能被2整除的数清0,

    // 再将3之后的所有能被3整除的数清0 ,

    // 以此类推,直到n为止。数组中不为0 的数即为素数。

    public static void main(String[] args) throws IOException

    {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String str = null;

    while ((str = br.readLine()) != null)

    {

    int num = Integer.parseInt(str);

    int[] array = new int[num - 1];

    for (int i = 0; i 

    {

    array[i] = i + 2;

    }   //将数组放进去

    for (int i = 2; i <= num / 2; i++)

    {

    for (int j = 0; j 

    {

    if (array[j] % i == 0 && array[j] != i)

    {

    array[j] = 0;

    }

    }

    }

    StringBuilder sb = new StringBuilder();

    int count = 0;

    for (int j : array)

    {

    if (j != 0)

    {

    sb.append(j).append(" ");

    } else

    {

    count++;

    }

    }

    System.out.println(sb.toString() + "\n" + count);

    }

    }

    }

    更多相关内容
  • Jupyter 使用列表实现筛选法求素数 使用列表实现筛选法求素数可以极大的提高计算机的运算速率。 maxNumber = int(input("请输入一个大于2的自然数:")) lst = list(range(2,maxNumber)) #最大整数的平方根 m = int...
  • 主要介绍了java使用筛选法求n以内的素数示例(java求素数),需要的朋友可以参考下
  • Eratosthenes筛选法求质数.rar
  • python语言对于计算机专业的学生,不管是计算机软件还是物联网,都是很重要的一种编程语言,python未来在人工智能方向上是会有很大的贡献程度...python学习—–使用列表实现筛选法求素数目录一、列表实现筛选法求素数
  • python使用筛选法求素数

    千次阅读 2021-10-31 00:24:22
    #自定义函数使用列表实现素数筛选法求素数 #素数x是指不能被2或自己整除的数,数学方法证明,只要不被2 ~ x**0.5(x的平方根)整除即可 def Era_Prime_Num(n): numl=[] #创建空列表用于存入求得素数 for i in range...

    不多说话,直接附代码

    #自定义函数使用列表实现素数筛选法求素数
    #素数x是指不能被2或自己整除的数,数学方法证明,只要不被2 ~ x**0.5(x的平方根)整除即可
    def Era_Prime_Num(n):
        numl=[]                         #创建空列表用于存入求得素数
        for i in range(2,n):            #遍历循环,循环左包含右不包含(要求小于n本身,所以右边为n)
            r = int(i ** 0.5)+1         #r为内循环右边界
            Flag=True                   #默认是素数,标记为True
            for j in range(2,r):
                if i % j == 0:          #如果i%j==0,i不为为素数
                    Flag=False          #标记为False
                    break               #直接跳出内循环
            if Flag==True:              #如果每一个内循环全循环完毕判断Flag是True
                numl.append(i)          #i就是素数并把i用append()函数存入列表尾部
        return numl
    num = int(input("Please input n:"))
    print("Result:", Era_Prime_Num(num))
    
    
    
    展开全文
  • [数值问题]素数筛选 内存限制:128 MB时间限制:1.000 S 题目描述 输入一正整数n(2<=n<=5*10^6),按顺序输出2到n范围内的所有素数。 输入 输入共一行一个数,表示n的值。 输出 输出若干行,每行5个...

    [数值问题]素数筛选

    内存限制:128 MB时间限制:1.000 S

    题目描述

    输入一正整数n(2<=n<=5*10^6),按顺序输出2到n范围内的所有素数。

    输入

    输入共一行一个数,表示n的值。

    输出

    输出若干行,每行5个素数,用空格隔开。

    样例输入

    20

    样例输出

    2 3 5 7 11
    13 17 19

    素数在很多应用领域有很重要的用途,寻找一个高效的算法十分重要。例如,找出10000以内的素数可能仅仅是为某个程序做的准备工作,为提高程序的效率,希望在尽可能短的时间内完成。下面介绍一个经典算法——筛选法求素数。

    主要思想是以空间换时间,是很常用的一种提高算法效率的方法。这是一种思想,不是一种算法。这种思想的主要应用有以下两种:
    第一种是将之前计算的结果保存起来,方便当前计算之用,从而降低计算量。这种思想的典型体现就是动态规划算法,从求解规模较小的子问题开始,逐步递推求解规模更大的子问题,每次计算都将得到的最优结果保存起来,在后面的计算中,利用前面的计算结果求得当前的最优值,然后再保存起来,如此递推下去。

    所谓筛选法是指从小到大筛去一个已知素数的所有倍数。以筛选法求10000以内的素数为例,根据素数2可筛去4、6、8、…、9998、10000等数,然后根据索数3可筛去9.6.
    12.15,…,9999等数,由于4已被筛去了,下一个用于筛选的素数是5…依此类推,最后剩余的就是10000以内的素数。

    具体实现代码如下:

    #include<stdio.h>
    #define N 5000000//根据题意开一个数组
    #include<math.h>
    int a[N+1];//全局变量数组
    void prime(int n);//筛选素数的函数
    int main(void)
    {
    	int n,i,b=0;
    	scanf("%d",&n);
    	prime(n);//使用函数筛选
    	for(i=1;i<=n;i++)
    	{
    		if(a[i]==1)//输出筛选后剩余的素数
    		{
    			printf("%d ",i);
    			b++;
    			if(b==5)//五个数一行
    			{
    				printf("\n");
    				b=0;//用完初始化
    			}
    		}
    	}
    	return 0;
     } 
    void prime(int n)
    {
    	int m=0,i,j;
    	for(i=0;i<n;i++)
    	a[i]=1;//给所有数赋值为1
    	a[0]=a[1]=0;//0和1不是素数
    	m=(int)sqrt(n);
    	for(i=2;i<=m;i++)//从二开始依次筛选2,3....的倍数
    	{
    		if(a[i]==1)//筛选过的就不需要进入循环了,如2的倍数有4,4已经被筛选了即a[4]==0不进入循环
    		{
    			for(j=2*i;j<n;j=j+i)
    			{
    				a[j]=0;//将不是素数的数赋值为0
    			}
    		}
    	}
     } 

    展开全文
  • 计算素数的一个方法是埃氏筛,它的算法理解起来非常简单:首先,列出从2开始的所有自然数,构造一个序列:2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...取序列的第一个数2,它一定是...

    计算素数的一个方法是埃氏筛法,它的算法理解起来非常简单:

    首先,列出从2开始的所有自然数,构造一个序列:

    2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取序列的第一个数2,它一定是素数,然后用2把序列的2的倍数筛掉:

    3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取新序列的第一个数3,它一定是素数,然后用3把序列的3的倍数筛掉:

    5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    取新序列的第一个数5,然后用5把序列的5的倍数筛掉:

    7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

    不断筛下去,就可以得到所有的素数。

    # 构造一个从3开始的奇数序列

    def _odd_iter():

    n = 1

    while True:

    n += 2

    yield n

    def _not_visible(n):

    return lambda x: x % n > 0

    def primes():

    yield 2

    it = _odd_iter()

    while True:

    n = next(it)

    yield n

    it = filter(_not_visible(n), it)

    for n in primes():

    if n < 1000:

    print(n)

    else:

    break

    logo.gif

    展开全文
  • C语言:筛选法求素数

    2022-05-22 16:07:30
    筛选法求n以内的素数筛选法求解过程为:将2~n之间的正整数放在数组内存储,将数组中2之后的所有能被2整除的数清0,再将3之后的所有能被3整除的数清0 ,以此类推,直到n为止。数组中不为0 的数即为素数。 输入...
  • 筛选法求素数模板

    2018-07-22 18:24:36
    #include&lt;iostream&gt; #include&lt;cmath&gt;...using namespace std;...///要求的素数的范围  bool flag[10000];  int m=sqrt(a+0.5);  for(int i=2;i&lt;=m;i++)  if(!flag...
  • 筛选法求素数-c++

    2021-04-02 20:27:33
    筛选法求n以内的素数筛选法求解过程为:将2~n之间的正整数放在数组内存储,将数组中2之后的所有能被2整除的数清0,再将3之后的所有能被3整除的数清0 ,以此类推,直到n为止。数组中不为0 的数即为素数。 输入...
  • 筛选法求素数

    千次阅读 多人点赞 2017-12-19 10:43:22
    用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的 数是素数,然后去掉它的倍数。依次类推,直到“筛子”为空时结束。如有: 1-100的数1...
  • 原理:素数,指在一个大于1的自然数...一个比较常见的求素数的办法是埃拉托斯特尼筛(the Sieve of Eratosthenes),说简单一点就是画表格,然后删表格,如图所示:从2开始依次往后面数,如果当前数字一个素数,那么...
  • python使用列表实现筛选法求素数

    千次阅读 2021-07-10 09:28:54
    使用列表实现筛选法求素数 实验目的 了解素数的定义 理解筛选法求解素数的原理 理解切片操作 熟练运行内置函数enumerate() 熟练运用内置函数filter() 理解序列解包的工作原理 熟悉选择结构和循环结构 实验内容...
  • python 用列表筛选法求素数

    千次阅读 多人点赞 2020-11-29 22:53:55
    import math def prime(n): alist=[x for x in range(2,n+1)] k=0 for i in range(0,math.floor(math.sqrt(n+1))): m=0 for j in range(2,n+1): ...print(“所得的素数为:”,alist) n = int(input(“请输入一个大于2
  • C语言筛选法求素数

    千次阅读 多人点赞 2020-04-01 14:13:50
    素数的定义:素数也即质数;在大于1的自然数中,除了1和他本身以外没有其他的因数,我们称之为素数。 问题:出1-100之内的素数方法1,利用定义直接遍历 #include<stdio.h> #include<math.h> //...
  • C++筛选法求素数(简单)

    千次阅读 2018-03-16 11:34:13
    筛选法求素数经常是求解其他问题的前提 代码: #include &lt;bits/stdc++.h&gt; using namespace std; const int N = 100001; int prime[N]{0}; int main() { for(int i=2;i!=N;++i) prime[i] = 1; ...
  • Java筛选法求素数

    千次阅读 2017-09-13 10:06:24
    给定一个正整数,编写程序计算有多少对质数的和等于输入的这个正整数,并输出结果。输入值小于1000。如,输入为10, 程序应该输出结果为2。(共有两对质数的和为10,分别为(5,5),(3,7)) 输入描述:输入包括一个整数n,...
  • 筛选法求素数&一般方法求素数&判断一个数是否是素数 1.判断一个数是否是素数 #include<stdio.h> #include<math.h> int main() { int n, i, k; printf("please enter a integer number");...
  • 利用筛选法求素数

    2021-04-10 22:58:26
    筛选法的基本思想:利用凡是2的任意倍数的数都不是素数,那么剩下的就是素数。利用标记法,假设MAXNUM=100个数里的所有素数,初始化时将所有数的标记位暂时赋值为1;然后将2的任意倍数的数的标记位暂时赋成0;最后...
  • //筛选法求素数 //放在数组里,如果是素数标记为1,并且打印出来 void IsPrime(int n) { int *pArr = (int *)malloc(n*sizeof(n)); int i = 0; int j = 0; assert(pArr != NULL); for(i = 0; i < n; i++)...
  • 编写程序,输入一个大于 2 的自然数,然后输出小于该数字的所有素数组成的列表。 源代码如下: # 素数函数 def prime_num(a): if a == 1: return -1 elif a == 2 or a == 3: return 1 else: for i in range...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,667
精华内容 5,066
关键字:

筛选法求素数

友情链接: JiSuanQi2.rar