首页 > 试题广场 >

N个素数

[编程题]N个素数
  • 热度指数：1185 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
写函数，输出前N个素数。不需要考虑整数溢出问题，也不需要使用大数处理算法。
算法知识视频讲解
添加回答
菜鸟葫芦娃头像 菜鸟葫芦娃 
import java.util.ArrayList;
import java.util.List;
public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List<Integer> getPrimes(int n) {
     List<Integer> ret = new ArrayList<Integer>();
        // ret.add(x);
        int number = Integer.MAX_VALUE;
        int counter = 0;
        for (int i = 2; i < number; i++) {
            if (n <= 0) {
                break;
            }
            counter = 0;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    counter++;
                    break;
                }
            }
            if (counter == 0) {
                ret.add(i);
                n--;
            }
        }
        return ret;
    }
}

发表于 2015-05-14 14:37:40 回复(1)
NST_Xx头像 NST_Xx 
package prime;
/**
 * 思路：从整数中提取前n个素数，放入ret中。放入ret条件是Boolean isPrimes(),return ret条件是count<=n-1
 */
import java.util.ArrayList;
import java.util.List;


public class Solution {

    public static void main(String[] args) {
        System.out.print(getPrimes(3));
    }
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public static List<Integer> getPrimes(int n) {
        int number = Integer.MAX_VALUE;
        int count = 0;
        List<Integer> ret = new ArrayList<Integer>();
        for(int i=0;i<number&&count<=n-1;i++){
            if(isPrime(i)){
                ret.add(i);
                count++;
            }
        }
        return ret;
    }

    public static boolean isPrime(int x){
        boolean flag = true;
        if(x<2)
            return false;
        else{
            for(int i=2;i<=(int)Math.sqrt(x);i++){
                if(x%i==0){
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }
}
发表于 2017-05-21 14:56:32 回复(0)
披萨大叔头像 披萨大叔 

	importjava.util.ArrayList;





	importjava.util.List;





	 





	publicclassSolution {





	    /**





	     * 获取n个素数





	     * n: 素数个数





	     * 返回：最小的N个素数





	     */





	    publicList<Integer> getPrimes(intn) {





	        List<Integer> ret = newArrayList<Integer>();





	        if(n == 0){





	            returnret;





	        }





	        ret.add(2);





	        n-=1;





	        // ret.add(x);





	        inti = 3;





	        while(n > 0){





	            if(isSuShu(i)){





	                ret.add(i);





	                n--;





	            }





	            i+=2;





	        }





	        returnret;





	    }





	     





	    publicbooleanisSuShu(intn){





	        intk = (int)Math.sqrt(n);





	        for(inti = 2; i <= k; i++){





	            if(n % i == 0){





	                returnfalse;





	            }





	        }





	        returntrue;





	    }





	}

发表于 2016-09-11 21:06:30 回复(0)
TPU-Lee头像 TPU-Lee
class Solution {
public:
    vector<int> getPrimes(int n){
        vector<int> ret;
        int cnt=0;
        for (int i=2;;i++){
            if (n <= 0) {
                break;
            }
            cnt = 0;
            for (intj=2;j<=sqrt(i);j++){
                if (i%j==0) {
                    cnt++;
                    break;
                }
            }
            if(cnt==0){
                ret.push_back(i);
                n--;
            }
        }
        return ret;
    }
};
发表于 2016-01-10 12:56:58 回复(0)
叶小鱼头像 叶小鱼
一个一个判断可以吗
发表于 2014-09-18 16:39:09 回复(1)
PeterChen__头像 PeterChen__
public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List<Integer> getPrimes(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        // ret.add(x);
        if(n < 2){
            return ret;
        }
        boolean isPrime = true;
        for(int i = 2; i < Integer.MAX_VALUE && ret.size() < n; i++){
            isPrime = true;
            for(int j = 2; j <= (int)Math.sqrt(i); j++){
                if(i%j == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime){
                ret.add(i);
            }
        }
        
        return ret;
    }
}
发表于 2020-04-25 01:17:56 回复(0)
－＞文艺范儿🎭头像 －＞文艺范儿🎭
如果输出大于0，那第一个必然是2，然后再开始循环获取新的素数。
为提高效率，一旦出现能整除的，马上跳出当前循环进行下一次循环比较。 
import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List<Integer> getPrimes(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        // ret.add(x);
       int m;
        int l = 0;
        int ii = Integer.MAX_VALUE;
        if(n > 1){
            ret.add(2);
            l = 1;
        }
        label:
        for(int i = 3; i <= ii && l < n; i += 2){
            m = 3;
            for(; m < i; m += 2){
                if(i % m == 0){
                    continue label;
                }
            }
            ret.add(i);
            l++;
        }
        return ret;
    }
}

发表于 2018-06-07 17:11:14 回复(0)
MonchiDluffy头像 MonchiDluffy
#include <vector>
using namespace std;
 
classSolution
{
public:
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
     
    bool isPrime(intx)
    {
        for(inti = 2; i <= sqrt(x); i++)
        {
            if(x % i == 0)
            {
                returnfalse;
            }
        }
        returntrue;
    }
     
    vector<int> getPrimes(intn)
    {
        vector<int> ret;
        ret.clear();
        if(n == 0)
        {
            returnret;
        }
        ret.push_back(2);
        if(n == 1)
        {
            returnret;
        }
        intcount = 1;
        for(inti = 3;; i += 2)
        {
            if(isPrime(i) == true)
            {
                count++;
                ret.push_back(i);
            }
            if(count == n)
            {
                break;
            }
        }
        returnret;
    }
};
发表于 2017-08-10 20:20:05 回复(0)
YuanCode头像 YuanCode 

	import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List < Integer > getPrimes(int n) {
		List < Integer > ret = new ArrayList < Integer > ();
		// ret.add(x);
		for (int i = 2; i < Integer.MAX_VALUE && ret.size() < n; i++) {
			boolean flag = true;
			int temp = (int)Math.sqrt(i);
			for (int j = 0; j < ret.size() && ret.get(j) <= temp; j++)
				if (i % ret.get(j) == 0) {
					flag = false;
					break;
				}
			if (flag)
				ret.add(i);
		}
		return ret;
	}
}
编辑于 2017-06-12 21:58:21 回复(0)
小白debug头像 小白debug 
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
	 
    vector<int> getPrimes(int n) {
        vector<int> ret;
		int d[800000]={0};
		int i,j,N=0;
		d[1]=d[0]=1;
		for(i=4;i<800000;i+=2)
			d[i]=1;
		for(i=3;i*i<800000;i+=2)
			if(!d[i])
			{
				for(j=i*i;j<800000;j+=2*i)
				{
					d[j]=1;
				}
				
			}
		for(i=0;i<800000;i++)
			if(!d[i])
			{  if(N==n)break;
				ret.push_back(i);
			   N++;
			}
		
		
        
        return ret;
    }
};

发表于 2016-09-30 18:03:59 回复(0)
code_pig头像 code_pig 
public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List<Integer> getPrimes(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        
		int sum = 0;
		int i = 1;
		while(n>sum){
			i++;
			for(int j=2;j<=i;j++){
				if(i%j ==0){
					if(i==j){
						ret.add(i);
						sum++;
					}else{
						break;
					}
				}

			}
		}        // ret.add(x);
        return ret;
    }

发表于 2016-09-18 15:28:09 回复(0)
tian-michael头像 tian-michael 
#! /bin/bash
declare -i lastnum=0

primelist="2"

if [ $# -gt 0 ];then
	(( lastnum+=$1 ))
	echo "positive primes up to $lastnum"
	if [ $lastnum -ge 2 ]; then
	echo "2"

	for n in `seq 3 2 $lastnum`
	do
		p=0
		for t in $primelist
		do
			(( remainder=n%t ))
			if [ $remainder -eq 0 ]; then
				p=1
				break
			fi
		done
		if [ $p -eq 0 ]; then
			echo $n
			if (( lastnum > (n * n) ));then
				primelist="$primelist $n"
			fi
		fi
	done
	fi
fi

发表于 2016-09-13 18:02:07 回复(0)
暴风赤红头像 暴风赤红 
import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    public List<Integer> getPrimes(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        for(int i=2;i<=Integer.MAX_VALUE;i++){
            int count=2;
            for(int j=2;j<=i/2;j++){
                if(i%j==0){
                    count++;
                    break;
                }
            }
            if(count==2){
                if(ret.size()==n){
                    break;
                }
                ret.add(i);
            }
        }
        return ret;
    }
}

发表于 2016-08-17 21:27:54 回复(0)
棉花汤头像 棉花汤 

	#include <vector>





	using namespace std;





	 





	classSolution {





	public:





	    /**





	     * 获取n个素数





	     * n: 素数个数





	     * 返回：最小的N个素数





	     */





	    bool IsPrimer(intn){





	        for(inti = 2;i*i<=n;++i)





	            if(n%i==0)





	                returnfalse;





	        returntrue;





	    }





	    vector<int> getPrimes(intn) {





	        vector<int> ret;





	        intst = 2;





	        while(n>0){





	            if(IsPrimer(st)){





	                ret.push_back(st);





	                ++st;





	                --n;





	            }





	            else





	                ++st;





	        }





	        returnret;





	    }





	};

发表于 2016-08-11 15:17:49 回复(0)
牛客485873号头像 牛客485873号 
#include<math.h>
#include<iostream>

int main()
{
    int n,i=0,k=0;
    cin>>n;
    while(n>k)
     {     ++i;
            if(i%2==0&&i!=2)continue;
           int j,flg;flg=1;
           for(j=3;j<=sqrt(i);j+=2)
           {
                    if(i%j==0){flg=0;  break;}      
           }
         if(flg==1){cout<<i<<" "; k++;} 
                  
     }
   return 0;
}

编辑于 2016-06-29 10:10:40 回复(1)
selfboot头像 selfboot 

#include <vector>
#include <iostream>
#include <climits>
using namespace std;
 
class Solution {
public:
    const int SHIFT = 5;
    const int MASK  = 0x1F;
    const int Max = INT_MAX;
    int bitmap[10000]{1,1,0,0,1,0};
 
    void set_not_prime(int num){
        bitmap[num >> SHIFT] |= (1<<(num&MASK));
    }
 
    bool not_prime(int num){
        return bitmap[num >> SHIFT] & (1<<(num&MASK));
    }
 
    /*
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    vector<int> getPrimes(int n) {
        vector<int> ret;
        int count = 0;
        int pos = 2;
        while(count < n){
            if(not_prime(pos)){
                pos ++;
                continue;
            }
            count += 1;
            ret.push_back(pos);
            int up = pos + pos;
            while(up < 320000){
                set_not_prime(up);
                up += pos;
            }
            pos += 1;
        }
        // ret.push_back(x);
        return ret;
    }
};

发表于 2016-03-26 15:44:02 回复(0)
L0L头像 L0L 
//筛选法，再利用bitmap位标示整数
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    vector<int> getPrimes(int n) {
        vector<int> ret;
        if(n<=1) return ret;
        long i,j;
        unsigned char arr[1<<13]={0};
        for(i=2;i<(1<<16);++i){
        	for(j=i+i;j<(1<<16);j=j+i){
        		arr[j/8]=arr[j/8]|(1<<(j%8));
			}
		}
		for(i=2;i<(1<<16)&&n>0;++i){
			if(!(arr[i/8]&(1<<(i%8)))){
				ret.push_back(i);
				--n;
			}
		}
        return ret;
    }
};

发表于 2015-08-26 16:54:31 回复(0)
九城城主头像 九城城主

思路：首先判断给出的n是否大于0，如果不是则直接返回ret。如果n > 0，则进行一下处理：

由于素数中只有2是偶数，其余素数都是奇数，因此将2先压入ret。定义奇整数x，要么是素数，要么是前面素数的倍数（比如3是素数，而9是奇数，但9是3的倍数，所以9不是素数。而13是奇数，但它不能够整除前面比它小的的任一一个素数，因此它是素数），只要当前奇整数x不能整除比它小的所有素数，那么它就是素数，然后将x压入ret，x的值+2，变为下一个奇数，继续判断。直到ret的长度等于n。
过程如下：
1、如果n <= 0，直接返回ret。
2、如果n > 0，先将2压入ret。令x = 3：
    1）如果ret的长度等于n，则返回ret；
    2）如果ret的长度小于n，对ret从i = 0 ~ n - 1遍历，判断是否有能够被x整除的素数，如果没有则将x压入ret，然后x值+ 2，返回1）；如果有则表示x不是素数，则将x值+ 2，继续判断ret中有没有可以整除x的素数。
完成之后返回ret。
代码如下所示：
#include <vector>
using namespace std;
class Solution {
public:
    /**
     * 获取n个素数
     * n: 素数个数
     * 返回：最小的N个素数
     */
    vector<int> getPrimes(int n) {
        vector<int> ret;
        // ret.push_back(x);
        if(n <= 0)
            return ret;
        ret.push_back(2);
        int i = 0;
        int x = 3;
        int len = ret.size();
        while(len < n)
            {
            //标志位--flag为1则表示没有新的素数压入ret，为0则表示有新的素数压入
            int flag = 1;
            while(flag)
            {
             for(i = 0; i < len; i ++)
             {
                 if(x % ret[i] == 0)
                    break;
             }
                if(i == len)  //i == len表示ret中没有可以整除x的素数
                {
                 flag = 0;  //标志位置0，跳出循环
                 ret.push_back(x); //x压入ret
                 len = ret.size();
                }
                x += 2;    //x += 2，变为下一个素数
            }
        }
        return ret;
    }
};
发表于 2015-08-19 10:19:44 回复(0)
iun头像 iun 
vector<int> getPrimes(int n) {
        vector<int> ret;
        // ret.push_back(x);
        int prime_cnt =0;
        for(int i=2;prime_cnt<n;i++){
            bool is_prime =1;
            for(int j=0;j<ret.size()&&(ret[j]*ret[j]<=i);j++){
                if(i%ret[j]==0){
                    is_prime =0;
                    break;
                }
            }
            if(is_prime){
                ret.push_back(i);
                prime_cnt++;
            }
        }
        return ret;
    }

编辑于 2015-08-15 12:01:39 回复(0)
咩咩jiang头像 咩咩jiang
运行超时，不知何解~>_<
vector<int> getPrimes(int n) {
        vector<int> ret;
        int i,count=0,flag=1;
        for(i=1;count<n;i++)
        {
            if(i==1||i==2)
            {
                ret.push_back(i);
                count++;
            }
            int k;
            for(k=2;k<=(int)sqrt(i);k++)
            {
                if(i%k==0)
                    flag=0;
            }
            if(flag==1)
            {
               ret.push_back(i); 
                count++;
            }
                 
        }
        // ret.push_back(x);
        return ret;
    }

发表于 2015-07-16 16:09:19 回复(1)
提交观点

问题信息

谷歌 编程基础 复杂度
来自：程序员智力算法笔试卷
难度：
25条回答 19724浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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