首页 > 试题广场 >

素数

[编程题]素数
  • 热度指数：21699 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1。

输入描述:
输入有多组数据。
每组一行，输入n。


输出描述:
输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1。
示例1

输入

100

输出

11 31 41 61 71
算法知识视频讲解
添加回答
Python
华科平凡头像 华科平凡

python solution:

def isSu(num):
    for i in range(2,num):
        if num%i==0:
            return False
    return True
while True:
    try:
        a=int(input())
        res=[]
        for i in range(11,a,10):
            if isSu(i):
                res.append(str(i))
        print(" ".join(res))

    except:
        break
发表于 2017-10-01 14:48:48 回复(1)
C++
牛客113649850号头像 牛客113649850号 
#include<iostream>
#include<cmath>

using namespace std;

const int N = 10000;

int a[N], an;

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i = 2;i < n;i++){
            int bound = sqrt(i);
            bool flag = true;
            for(int j = 2;j <= bound;j++){
                if(i % j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag&&i % 10 == 1) a[an++] = i;
        }
        if(an > 0){
            for(int i = 0;i < an - 1;i++) printf("%d ", a[i]);
            printf("%d\n", a[an - 1]);
        }else{
            printf("-1\n");
        }
    }
    return 0;
}
发表于 2022-01-25 16:10:10 回复(0)
C/C++
拜托求求给一个offer头像 拜托求求给一个offer 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

vector<int> prime;

void initial(int n)
{
    bool *arr = new bool[n];
    for (int i = 2; i < n; i++)
    {
        arr[i] = true;
    }
    for (int i = 2; i < n; i++)
    {
        if (!arr[i])
        {
            continue;
        }
        prime.push_back(i);
        for (int j = 2 * i; j < n; j += i)
        {
            arr[j] = false;
        }
    }
    delete[] arr;
}

int main()
{
    int n, total, tmp;
    while (cin >> n)
    {
        initial(n);
        total = 0;
        for (int i = 0; i < prime.size(); i++)
        {
            if (prime[i] % 10 == 1)
            {
                total++;
            }
        }
        if (total == 0)
        {
            cout << -1 << endl;
        }
        else
        {
            tmp = 0;
            for (int i = 0; i < prime.size(); i++)
            {
                if (prime[i] % 10 == 1)
                {
                    tmp++;
                    if (tmp == total)
                    {
                        printf("%d\n", prime[i]);
                    }
                    else
                    {
                        printf("%d ", prime[i]);
                    }
                }
            }
        }
        prime.clear();
    }
    return EXIT_SUCCESS;
}

发表于 2021-02-19 17:31:19 回复(0)
C/C++
胡桃夹子🎈头像 胡桃夹子🎈 
#include<iostream>
using namespace std;
#include<vector>
int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> v;
		if (n <= 11)
		{
			cout << -1 << endl;
			continue;
		}
		bool* mark = new bool[n];//筛法标记数组
		for (int k = 0; k < n; k++)
			mark[k] = 1;//默认都是素数
		mark[0] = false;
		mark[1] = false;
		
		for (int i = 2; i < n; i++)
		{
			if (mark[i] == 0)//非素数 跳过
				continue;
			if(i % 10 == 1)
				v.push_back(i);//个位为1的素数
			for (int j = 2 * i; j < n; j += i)//素数的倍数为非素数
				mark[j] = false;
		}
		for (int t = 0;t < v.size(); t++)
			if (t != v.size())
				cout << v[t] << " ";
			else
				cout << v[t];
		cout << endl;

		delete[] mark;
		v.clear();
	}
	return 0;
}

筛法
编辑于 2020-05-06 13:00:20 回复(0)
Java
LHC0512头像 LHC0512
Java  
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            boolean flag = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag && String.valueOf(i).endsWith("1")) list.add(i);
        }
        if (list.isEmpty()) System.out.println(-1);
        else for (Integer i : list) System.out.print(i + " ");
    }
}


发表于 2020-03-18 15:18:23 回复(1)
C/C++
小萝卜特糖泥头像 小萝卜特糖泥 
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100001;

vector<int> allprime,prime;
bool p[maxn]={0};
void findprime(int n){
	for(int i=2;i<n;i++)
	{
		if(p[i]==false)
		{
			allprime.push_back(i);
		
			for(int j=i+i;j<n;j+=i)
			{
				p[j]=true;
			}
		}
	}
}
int main()
{
	int n;
	while(cin>>n)
	{
		findprime(n);
    	for(int i=0;i<allprime.size();i++)
	   {
	   	if(allprime[i]%10==1)
	   	    {
	   		prime.push_back(allprime[i]);
	     	}
		
       }
       if(prime.empty())
       {
       	cout<<"-1"<<endl;
       	continue;
	   }
    	for(int i=0;i<prime.size()-1;i++)
    	{
    		cout<<prime[i]<<" "; 
    	
		}
		cout<<prime[prime.size()-1]<<endl;
    	prime.clear();
    	allprime.clear();
    	
	}
	
	return 0;
 } 


编辑于 2020-03-12 10:29:24 回复(0)
C/C++
算法小屁孩头像 算法小屁孩 
int a[10001],b[10001],s,n;
int main(){
    for(int i=2;i<=10000;i++){
        if(b[i]==1)
            continue;
        a[s++]=i;
        for(int j=i*i;j<=10000;j+=i)
            b[j]=1;
    }
    while(scanf("%d",&n)!=EOF){
        int m=0;
        for(int i=0;a[i]<n;i++)
            if(a[i]%10==1){
                m=1;
                printf("%d ",a[i]);
            }
        if(m==0)
            printf("-1");
        printf("\n");
    }
}
发表于 2019-03-15 17:06:01 回复(0)
神秘帅哥头像 神秘帅哥
#include<stdio.h>
#include<math.h>
bool issu(int a){
    double b = sqrt(a);
    int tag = 1;
    for(int i = 2;i <= b;i ++){
        if(a % i == 0)
            tag = 0;
    }
    if(tag == 0)
        return false;
    else
        return true;
}
bool isone(int a){
    if(a % 10 == 1)
        return true;
    else
        return false;
}
int main(){
    int n;
    int buf[10000];
    int size = 0;
    while(scanf("%d",&n) != EOF){
        for(int i = 2; i < n; i ++){
            if(issu(i) && isone(i)){
                buf[size++] = i;
            }
        }
        for(int i = 0;i < size;i ++)
            printf("%d ",buf[i]);
        printf("\n");
    }
    return 0;
}

发表于 2019-03-05 17:00:30 回复(0)
C/C++
@**@头像 @**@
//在王道上学到的素数筛选法
#include<stdio.h>
int prime[10001];//存储素数的数组
int primesize=0;//记录素数的个数
int mark[10001];//标记是否是素数

void init(){
    for(int i=2;i<=10000;i++)
        mark[i]=false;//初始化，所有数目前均为素数
    for(int i=2;i<=10000;i++){
        if(false==mark[i]){
            prime[primesize++]=i;//记录素数
            for(int j=i*i;j<=10000;j+=i){       
                //在这里，从 i*i 开始，因为 i*k (k<i) 也是k的素因数的倍数
                mark[j]=true;//置素数的倍数均为非素数
            }
        }
    }
} 

int main(){
    init();//求2-10000之间的所有素数，记录在全局变量prime中
    int n;
    while(scanf("%d",&n)!=EOF){
        bool isOutput=false;
        for(int i=0;i<primesize;i++){
            if(prime[i]<n && prime[i]%10==1){//1-n之间的素数，且个位为1
                if(false==isOutput){
                    isOutput=true;
                    printf("%d",prime[i]);
                }
                else printf(" %d",prime[i]);
            }
        }
        if(false==isOutput)
            printf("-1\n");
        else printf("\n");
    }
    return 0;
}

发表于 2018-03-21 20:27:50 回复(0)
时光是影子的眼头像 时光是影子的眼 
//王道优化后
#include<stdio.h>
#include<math.h>
int prime[10001];
int primeSize = 0;
bool mark[10001] = { 0 };
void init() {
    for (int i = 2; i <= 10000; i++) {
        if (mark[i] == 1) continue;
        prime[primeSize++] = i;
        for (int j = i * i; j<10001; j += i)
        {
            mark[j] = true;
        }
    }
}
int main() {
    init();
    int n;
    while (scanf("%d", &n) != EOF) {
        bool tag1 = 0;
        for (int i = 1; i < primeSize; i++) {
            if (prime[i]<n  && prime[i] % 10 == 1) {
                if (tag1 == 0) {
                    printf("%d", prime[i]);
                    tag1 = 1;
                }
                else printf(" %d", prime[i]);
            }
        }
        if (tag1 == 0)printf("%d", -1);
        printf("\n");
    }
    return 0;
}

发表于 2018-03-06 12:42:30 回复(0)
huangju头像 huangju
#include <stdio.h>
#include <math.h>
bool prime(int a){
    if(a<=1)return false;
    int b=(int)sqrt(a)+1;
    for(int i=2;i<=b;++i)
        if(a%i==0)return false;
    return true;
}
int main()
{
    int x;
    while(scanf("%d",&x)!=EOF)
    {
        if(x<12){printf("-1\n");break;}
        int a[1000],size=0;//估计小于10000且符合条件的素数小于1000个，只要保证数组足够大
        for(int i=11;i<x;i+=10){
            if(prime(i)&&i%10==1)a[size++]=i;
        }
        printf("%d",a[0]);// 格式比较麻烦 要千万注意
        if(size>1)for(int i=1;i<size;++i)
            printf(" %d",a[i]);
        printf("\n");
    }
    return 0;
}

运行时间：3ms

占用内存：428k

发表于 2018-01-17 23:36:11 回复(2)
kestars头像 kestars 
#include<iostream>
#include<vector>
using namespace std;
void print(vector<int> result){
    if(result.empty()){
        cout<<-1<<endl;
    }else{
        for(int i=0;i<result.size()-1;i++){
            cout<<result[i]<<" ";
        }
        cout<<result[result.size()-1]<<endl;
    }
}
int main(){
    int n;
    while(cin>>n){
        vector<int> result;
        result.clear();
        int prime=11;
        while(prime<n){
            int flag=1;
            for(int i=2;i<prime/2;i++){
                if(prime%i==0){
                    flag=0;
                }
            }
            if(flag==1){
                result.push_back(prime);
            }
            prime=prime+10;
        }
        print(result);
    }
}

发表于 2017-10-09 00:32:11 回复(0)
Python
QuestCompleted头像 QuestCompleted 
def isPrime(n):
    return not [i for i in xrange(2, int(n ** 0.5) + 1) if n % i == 0]
     
table = [x for x in xrange(2, 10000) if isPrime(x) and str(x)[-1] == '1']
         
try:
    while 1:
        n = input()
        if n <= 11:
            print -1
        else:
            result = []
            for i in table:
                if i >= n:
                    break
                else:
                    result.append(str(i))
            print ' '.join(result)
except:
    pass

发表于 2016-12-26 18:20:21 回复(0)
C/C++
练习时长两年半的Java练习生头像 练习时长两年半的Java练习生 
#include<stdio.h>
int main (){//the shorter,the better.
    int n,i,count;int hash[307]={11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491, 521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031, 1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381, 1451, 1471, 1481, 1511, 1531, 1571, 1601, 1621, 1721, 1741, 1801, 1811, 1831, 1861, 1871, 1901, 1931, 1951, 2011, 2081, 2111, 2131, 2141, 2161, 2221, 2251, 2281, 2311, 2341, 2351, 2371, 2381, 2411, 2441, 2521, 2531, 2551, 2591, 2621, 2671, 2711, 2731, 2741, 2791, 2801, 2851, 2861, 2971, 3001, 3011, 3041, 3061, 3121, 3181, 3191, 3221, 3251, 3271, 3301, 3331, 3361, 3371, 3391, 3461, 3491, 3511, 3541, 3571, 3581, 3631, 3671, 3691, 3701, 3761, 3821, 3851, 3881, 3911, 3931, 4001, 4021, 4051, 4091, 4111, 4201, 4211, 4231, 4241, 4261, 4271, 4391, 4421, 4441, 4451, 4481, 4561, 4591, 4621, 4651, 4691, 4721, 4751, 4801, 4831, 4861, 4871, 4931, 4951, 5011, 5021, 5051, 5081, 5101, 5171, 5231, 5261, 5281, 5351, 5381, 5431, 5441, 5471, 5501, 5521, 5531, 5581, 5591, 5641, 5651, 5701, 5711, 5741, 5791, 5801, 5821, 5851, 5861, 5881, 5981, 6011, 6091, 6101, 6121, 6131, 6151, 6211, 6221, 6271, 6301, 6311, 6361, 6421, 6451, 6481, 6491, 6521, 6551, 6571, 6581, 6661, 6691, 6701, 6761, 6781, 6791, 6841, 6871, 6911, 6961, 6971, 6991, 7001, 7121, 7151, 7211, 7321, 7331, 7351, 7411, 7451, 7481, 7541, 7561, 7591, 7621, 7681, 7691, 7741, 7841, 7901, 7951, 8011, 8081, 8101, 8111, 8161, 8171, 8191, 8221, 8231, 8291, 8311, 8431, 8461, 8501, 8521, 8581, 8641, 8681, 8731, 8741, 8761, 8821, 8831, 8861, 8941, 8951, 8971, 9001, 9011, 9041, 9091, 9151, 9161, 9181, 9221, 9241, 9281, 9311, 9341, 9371, 9391, 9421, 9431, 9461, 9491, 9511, 9521, 9551, 9601, 9631, 9661, 9721, 9781, 9791, 9811, 9851, 9871, 9901, 9931, 9941,10000};
    for(;~scanf("%d",&n);)
        for (count=0,i = 0; i <306;hash[i]<n?(hash[i+1]>=n?printf("%d\n",hash[i]):printf("%d ",hash[i]),++count):count==0?printf("-1\n"):0,i++);
}

发表于 2018-01-13 10:31:59 回复(0)
C/C++
老子是帮主头像 老子是帮主 
筛选法求素数：用一个数组记录某个数是不是素数，初始认为所有数都是素数，然后从
前向后扫描数组，扫描到当前位置时标志位为true的为素数，保存这个素数，并且所有
是这个素数倍数的数都可以排除出素数的队列，将相应的标志位置为false。例如当扫描
到2时（2是素数），保存2，那么2之后的2×2,3×2，...，都不再是素数了，当扫描到
第i个数的时候，如果相应的标志位为true，保存第i个数，之后的2×i,3×i,...,都不
再可能是素数了。一定要从第2个"i"开始遍历吗?不是的，还能更快，扫描到第i个数的
时候，需要依次把 2×i,3×i,...,s×i,i×i,g×i,...等标志位都置为false，其中
2 <= s < i，g > i，而2×i在之前扫描到2的时候已经被重置(false)，3×i在之前扫
描到3的时候已经被重置，...，s×i在之前扫描到s的时候已经被重置，因此只需要从
i×i的位置开始向后重置标志位。
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int nMax = 10000;

int main(){
    //初始认为所有数字都是素数
    vector<bool> isPrime(nMax + 1, true);
    vector<int> prime;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= nMax; i++){
        if (isPrime[i])
            prime.push_back(i);
        for (int j = i * i; j <= nMax; j += i)
            isPrime[j] = false;
    }

    int n;
    while (cin >> n){
        int count = 0;
        for (int i = 0; i < prime.size() && prime[i] < n; i++){
            string s = to_string(prime[i]);
            if (s[s.size() - 1] == '1'){
                count++;
                if (count == 1)
                    cout << prime[i];
                else
                    cout << " " << prime[i];
            }
        }
        if (count == 0)
            cout << -1 << endl;
        else
            cout << endl;
    }
    return 0;
}

编辑于 2018-03-22 19:37:19 回复(2)
C/C++
Senjie头像 Senjie 
#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        n>11 ? cout<<11:cout<<-1;
        for(int i=31;i<n;i+=10)
        {
            for(int j=2;j*j<i;j++)
            {
                if(i%j==0)
                    break;
                else if((j+1)*(j+1)>i)
                    cout<<' '<<i;
            }
        }
        cout<<endl;
    }
}
发表于 2018-08-16 14:17:09 回复(0)
小陈也只是想要一个实习罢了头像 小陈也只是想要一个实习罢了 
//注意一下判断素数时只需要判断到sqrt(n)即可
#include<bits/stdc++.h>
using namespace std;
bool judge(int n){
    if(n==1) return 0;
    if(n==2) return 1;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0)
            return 0;
    return 1;
}
int main(){
    int n;
    while(cin>>n){
        int count=0;
        for(int i=2;i<n;i++)
            if(judge(i)&&i%10==1){
                cout<<i<<" ";
                count++;
            }
        cout<<endl;
        if(count==0)
            cout<<"-1"<<endl;
    }
}

发表于 2020-01-13 22:30:56 回复(0)
绫清竹头像 绫清竹
C++ 完整12行代码, 求打破！ 
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    while (cin >> n) 
        for (int i = 11; i < n; i += 10) 
            for (int j = 2; j <= sqrt(i); ++j) {
                if (i % j == 0) break;
                else if ((j + 1) > sqrt(i)) cout << i << ' ';
            }
}


编辑于 2021-02-03 18:04:14 回复(1)
C/C++
猫猫猫1头像 猫猫猫1
#include<bits/stdc++.h>
using namespace std;

const int Max=10001;
bool a[Max];

void Initial() {
    for(int i=0; i<Max; i++) {
        a[i]=true;
    }
    a[0]=false;
    a[1]=false;
    for(int i=2; i<Max; i++) {
        if(!a[i]) {
            continue;
        }
        for(int j=i*i; j<Max; j+=i) {
            a[j]=false;
        }
    }
    return ;
}

int main() {
    int n;
    Initial();
    while(cin>>n) {
        bool isoutput=false;
        for(int i=0; i<n; ++i) {
            if(a[i]) {
                if(i%10==1) {
                    cout<<i<<" ";
                    isoutput=true;
                }
            }
        }
        if(!isoutput) {
            cout<<"-1";
        }
        cout<<endl;
    }
    return 0;
}
发表于 2022-10-06 22:25:31 回复(2)
C++
漫山Ms头像 漫山Ms 
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=11;i<n;i+=10)//最小质数为11
        {
            int bound=sqrt(i);//上限
            bool flag=true;
            for(int j=2;j<=bound;j++)
                if(i%j==0)
                {
                    flag=false;
                    break;
                }
            if(flag)
                cout<<i<<" ";
        }
        cout<<endl;
    }
    return 0;
}

发表于 2022-03-08 10:34:17 回复(1)
提交观点

问题信息

基础数学
难度：
144条回答 10056浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号