c语言素数的幸运数,历届试题幸运数

蔚落 2022-10-15 05:54 146阅读 0赞

题目描述

问题描述

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成

首先从1开始写出自然数1,2,3,4,5,6,....

1 就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除，变为：

1 \_ 3 \_ 5 \_ 7 \_ 9 ....

把它们缩紧，重新记序，为：

1 3 5 7 9 .... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ...

此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...)

最后剩下的序列类似：

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...

输入格式

输入两个正整数m n, 用空格分开 (m < n < 1000\*1000)

输出格式

程序输出 位于m和n之间的幸运数的个数(不包含m和n)。

样例输入1

1 20

样例输出1

5

样例输入2

30 69

样例输出2

8

算法思路

这道题解题方法起始在题目中已经提到了用筛法，可以直接模拟题目的要求来算出结果。注意的是：如果幸运数选到1则忽视它用2代替，因为在素数中任何数除1都是整除的无意义。

具体代码

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Scanner;

public class LukyNum \{

public static void main(String\[\] args) \{

Scanner input =new Scanner(System.in);

int m=input.nextInt(),n = input.nextInt();

LinkedList linklist = new LinkedList<>();

LinkedList nextlist;

int posi = 0;//选第几个幸运数由于我用的是链表因此从0开始计数

//不管m，先求 出1-n之间所有的幸运数，最后再统计m-n之间有多少个数就可以了

for (int i = 1; i < n; i++)

linklist.add(i);

int nowlucky;//当前的幸运数

while (posi < linklist.size()) \{

nextlist = new LinkedList<>();

if (posi == 0)//如果幸运数是第一个数则用2代替

nowlucky = linklist.get(1);

else

nowlucky = linklist.get(posi);

Iterator iter = linklist.iterator();

int count = 0;

while (iter.hasNext()) \{

count++;

if (count % nowlucky == 0) \{

iter.next();

continue;

\}

nextlist.add(iter.next());

\}

linklist = nextlist;

posi++;

\}

input.close();

//统计不在m-n范围内的数

int outrangecount=0;

Iterator liter = linklist.iterator();

while(liter.hasNext())

\{

if(liter.next()>m)

break;

outrangecount++;

\}

//总的幸运数的个数-不在范围内的得到m-n范围内幸运数个数

System.out.println(linklist.size()-outrangecount);

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，146人围观）

还没有评论，来说两句吧...

相关阅读

相关华为OD机试 C++【计算幸运数】

遍历每个指令，首先小明站在原点，其坐标值为0。在每一步移动后，更新当前坐标值，并将其与之前的最大坐标值进行比较，从而找到游戏过程中的最大坐标值。给定一组指令和一个幸运数，...

妖狐艹你老母/ 2024年04月24日 14:57/ 0 赞/ 47 阅读

相关蓝桥杯幸运数

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,… 1 就是第一个幸运数。我们从2这个数开始。把所

超、凢脫俗/ 2024年03月30日 16:48/ 0 赞/ 42 阅读

相关历届试题幸运数暴力模拟

问题描述幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,.... 1 就是第一个幸运数。我们

本是古典何须时尚/ 2024年02月17日 20:50/ 0 赞/ 14 阅读

相关 c语言素数的幸运数,历届试题幸运数

题目描述问题描述幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成首先从1开始写出自然数1,2,3,4,5,6,.... 1 就是第一个幸运数。

蔚落/ 2022年10月15日 05:54/ 0 赞/ 147 阅读

相关幸运数

幸运数 Time Limit: 1000ms Memory limit: 262144K 有疑问？点这里^\_^ 题目描述如果，a是幸运数，b是幸运数，那么

朴灿烈づ我的快乐病毒、/ 2022年08月14日 05:36/ 0 赞/ 123 阅读

相关幸运素数

幸运素数 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 Naix\_x喜欢幸运数。我们都知

一时失言乱红尘/ 2022年08月10日 08:42/ 0 赞/ 155 阅读

相关历届试题幸运数

问题描述幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,.... 1 就是第一个幸运数。我们

痛定思痛。/ 2022年06月18日 11:49/ 0 赞/ 154 阅读

相关幸运数

小明同学学习了不同的进制之后，拿起了一些数字做起了游戏。小明同学知道，在日常生活中我们最常用的是十进制数，而在计算机中，二进制数也很常用。现在对于一个数字x，小明同学

绝地灬酷狼/ 2022年06月12日 06:11/ 0 赞/ 126 阅读

相关蓝桥杯训练历届试题幸运数（直接暴力，还用个锤子的堆）

问题描述幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。首先从1开始写出自然数1,2,3,4,5,6,.... 1 就是第一个幸运数。我们

喜欢ヅ旅行/ 2022年03月14日 20:57/ 0 赞/ 207 阅读

相关历届试题幸运数

思路分析初始化，首先筛掉所有偶数用l标记当前为第几个幸运数用p来标记已经剔除的数的个数，并正确将后面的数字移动。最后遍历计数m,n之间的数

「爱情、让人受尽委屈。」/ 2022年03月06日 18:54/ 0 赞/ 210 阅读