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

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

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__

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

  #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


	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

#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

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

#! /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号

#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

#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

//筛选法，再利用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

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

运行超时，不知何解~>_<

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)

N个素数

问题信息

热门推荐

通过挑战的用户

相关试题