首页 > 试题广场 >

编程量① 难度性能要求** (1秒)

[问答题]

编程量*^① 难度* 性能要求** (1秒)

聪聪在研究素数, 可是为搞清一些素数究竟在素数集合中排名老几, 伤透了脑筋。还是你帮他编个程序搞定吧, 否则, 他慢腾腾慢腾腾地数, 数到什么时候去?!

聪聪把素数放在一个叫 prime.txt 的文件中,里面大概有上千个正整数,每个正整数N(1≤N≤1000000)占1行。运行结果也是每个数占1行,不过,结果中的每个数实际上是输入的正整数在素数集合中的排名, 如果输入的不是素数(这太有可能了)那就输出一个0来表示。

样本输入文件的内容和输出结果示例于下:

推荐

Smizy

二分搜索版：

//===================================
//EX0601_1.cpp
//素数的排位(二分搜索版）
//===================================
#include<stdlib.h>
#include<stdio.h>
//-----------------------------------
const int nPrime = 78498;
int p[nPrime] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
//-----------------------------------
bool isPrime(int n){
  for(int j=1; p[j]*p[j]<=n; j++)
    if(n%p[j] ==0) return false;
  return true;
}//-----------------------------------
int comp(const void* p1,const void* p2){
  return *(int*)p1 - *(int*)p2;
}//----------------------------------
int main(){
  for(int i=67,m=18; i<1000000; i+=2)
    if(isPrime(i))
      p[m++]=i;
  freopen("prime.txt","r",stdin);
  for (int a, *ptr; scanf("%d ", &a) ! =EOF ){
    ptr = (int*)bsearch(&a, p, nPrime, sizeof(int), comp);
    printf("%d\n", (ptr ? ptr-p+1 : 0));
  }
}//==================================

向量版：

//===================================
//EX0601_2.cpp
//素数的排位（向量版）
//===================================
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
//-----------------------------------
int main() {
  vector<int> p(1000001,1);
  for(int i=2; i<=997; ++i)
    if(p[i])
      for(int j=i*i; j<=1000000; j+=i)
        p[j]=0
  for(int i=2,j=1; i<1000001; ++i)
    if(p[i]) p[i]=j++;
  ifstream cin("prime.txt");
  for(int a; cin>>a; )
    cout<<p[a]<<"\n";
}//==================================

数组版：

/===================================
//EX0601_3.cpp
//素数的排位（数组版）
//===================================
#include<stdio.h>
//-----------------------------------
int p[1000001];
int main() {
  for(int i=2; i<=997; ++i)
    if(!p[i])
      for(int j=i*i; j<=1000000; j+=i)
        p[j]=1
  for(int i=2,j=1; i<1000001; ++i)
    p[i] = (p[i]?0:j++);
  freopen("prime.txt","r",stdin);
  for(int a; scanf("%d ",&a) !=EOF; )
    printf("%d\n",p[a]);
}//==================================

发表于 2018-05-07 20:36:58 回复(0)