令 P_i 表示第 i 个素数。现任给两个正整数 M≤N≤10⁴，请输出 P_M 到 P_N 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 P_M 到 P_N 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

解题思想：

1.使用常规的素数判断方法进行判断，可以进一步优化为埃氏筛法

2.注意题目的边界，对各种输出的格式进行判断

时间复杂度：O(NlogN)

代码如下（Python）：

import math
 
Start, End = map(int, input().split())
PrimeJudge = True  # 标记该数是否为素数，默认为是
PrimeCount = 0  # 记录当前素数的位置
PrimeNumber = list()  # 存储素数的列表
PrintCount = 0  # 控制输出的计数
for i in range(2, 200000):#遍历一个足够满足条件的边界
    PrimeJudge = True  # 每次判断一个数就重置标记
    for j in range(2, int(math.sqrt(i))+1):
        if i % j == 0:
            PrimeJudge = False
            break
    if PrimeJudge == True:
        PrimeCount += 1
        if Start <= PrimeCount <= End:#该素数满足范围
            PrimeNumber.append(i)
    if PrimeCount > End:#素数个数已经超出范围
        break
for i in range(len(PrimeNumber)):#按题目格式输出
    PrintCount += 1
    if i == len(PrimeNumber) - 1:
        print(PrimeNumber[len(PrimeNumber) - 1])
    elif PrintCount < 10:
        print(PrimeNumber[i], end=" ")
    else:
        print(PrimeNumber[i])
        PrintCount = 0

使用Python，即使已经降到NlogN的时间复杂度，仍会超时。

代码如下（C）：

#include<stdio.h>
#include<math.h>
int main(void)
{
	int Start,End;
	scanf("%d %d",&Start,&End);
	int count = 1;//记录素数的位置，默认为1，2是第一个素数
	int printcount = 0;//标记输出的情况
	if(Start==1)//对特例进行判断，用不同的格式输出
	{
		if(End == 1)//只输出第一个素数
		{
			printf("2");
		}
		else
		{
			printf("2 ");
			printcount++;	
		}
	}
	for(int i=3;i<200000;i++)//定义足够大的边界
	{
		int primejudge = 1;//标记该数是否为素数，默认为是
		for(int j=2;j<sqrt(i)+1;j++)
		{
			if(i%j==0)//该数能被1和自己以外的数整除
			{
				primejudge = 0;//改变标记
				break;
			}
		}
		if(primejudge == 1)//该数是素数
		{
			count++;
			if(count >= Start && count <= End)//该素数所在的位置符合输入的条件
			{
				if(printcount < 9)//输出不需要换行
				{
					if(count == End)//该素数是输入的边界
					{
						printf("%d",i);
					}
					else
					{
						printf("%d ",i);
					}
					printcount++;
				}
				else//输出可能需要换行
				{
					if(count == End)//该素数是输入的边界也是一行的最后一个输出
					{
						printf("%d",i);
					}
					else
					{
						printf("%d\n",i);
					}
					printcount = 0;
				}
			}
			if(count > End)//寻找的范围超过输入的边界
			{	
				break;
			}	
		}
	}
	return 0;
}

< >

评论板

共有 12 条评论

fruinly

However, bone health can become compromised by ageing and or the presence of underlying medical conditions how does azithromycin work In addition, on her 2nd, 3rd, and 4th fingernails bilaterally, clinicians noticed a single transverse white line, parallel to the lunula

2023-03-05 05:13 回复
engarma

Who knew that the national teacher was beaten and almost died after only three face to face encounters buy cialis non prescription

2023-04-29 12:11 回复
cheap louis vuitton online

I just wanted to thank you for the fast service. alternatively they look great. I received them a day earlier than expected. just like I will definitely continue to buy from this site. you ultimately choose I will recommend this site to my friends. Thanks!
cheap louis vuitton online https://www.bestlouisvuittonoutlet.com/

2023-04-30 17:07 回复
cheap louis vuitton bags

I just wanted to thank you for the fast service. actually they look great. I received them a day earlier than expected. enjoy the I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
cheap louis vuitton bags https://www.louisvuittonsoutletstore.com/

2023-04-30 20:11 回复
cheap jordans online

I just wanted to thank you for the fast service. in addition to they look great. I received them a day earlier than expected. for instance I will definitely continue to buy from this site. either way I will recommend this site to my friends. Thanks!
cheap jordans online https://www.realjordansretro.com/

2023-04-30 23:57 回复
louis vuitton outlet

I just wanted to thank you for the fast service. or alternatively they look great. I received them a day earlier than expected. exactly like the I will definitely continue to buy from this site. either way I will recommend this site to my friends. Thanks!
louis vuitton outlet https://www.cheapreallouisvuitton.com/

2023-05-01 09:17 回复
cheap louis vuitton outlet

Read reviews and was a little hesitant since I had already inputted my order. otherwise but thank god, I had no issues. themselves received item in a timely matter, they are in new condition. no matter what so happy I made the purchase. Will be definitely be purchasing again.
cheap louis vuitton outlet https://www.louisvuittonsoutlet.com/

2023-05-16 01:07 回复
cheap louis vuitton handbags

Read reviews and was a little hesitant since I had already inputted my order. while well as but thank god, I had no issues. such as received item in a timely matter, they are in new condition. either way so happy I made the purchase. Will be definitely be purchasing again.
cheap louis vuitton handbags https://www.louisvuittonsoutletonline.com/

2023-05-16 09:44 回复
cheap jordans for sale

Read reviews and was a little hesitant since I had already inputted my order. or perhaps a but thank god, I had no issues. such as received item in a timely matter, they are in new condition. blue jays so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans for sale https://www.realjordansshoes.com/

2023-05-17 07:01 回复
Preliaf

When we mentioned wide state variations, Schank said It s noticeable if you have traveled to other cities or states that every place has their own rules that they are really, really adamant about, and you have no idea what those rules are cialis without a doctor’s prescription Interestingly, the four patients with recurrent VTE who received only IVC filters had longer MTRs 6

2023-06-01 01:22 回复
Preliaf

Member, Ontario Medical Association prix levitra 10 mg

2023-06-12 01:42 回复
Fsmppgw

I know how you feel just wanting your body to do the work itself and I ve thought about natural, herbal alternatives cialis daily

2023-07-14 04:21 回复

PAT乙级:1013 数素数