一百万以内的素数

#include <iostream>
#include <vector>
using namespace std;
#define MAX 1000000

long s[MAX+1];

void init()//构造一个100万以内的素数表
{
   int i, j;
   for (i = 2; i <= MAX; i++)
   {
       s[i] = 1;
   }
   s[0] = s[1] = 0; //0和1肯定不是素数

   for (i = 2; i <= MAX; i++)
   {
       if (s[i] == 1)
       {
           for (j = 2 * i;  j <= MAX; j += i)
               s[j] = 0;
       }
   }
}

int main()
{
    init();//构造一个100万以内的素数表
    long a, b;
    int tmp = 0;
    int i, j;
    vector<int> vec;

 	while (cin >> a >> b)
 	{
 	    for (i = a; i <= b; i++)
 	    {
 	        if (s[i] == 1)
 	           tmp++;
 	    }
 	    vec.push_back(tmp);
 	    tmp = 0;
    }

    i = 1;
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
 	{
	 	cout << "Case " << i++ << ":" << endl;
	 	cout << *it << endl;
	}

 	//system("pause");
 	return 0;
}
时间: 2025-01-10 03:58:02

一百万以内的素数的相关文章

.net-C#.Net怎么求100以内的素数?

问题描述 C#.Net怎么求100以内的素数? C#.Net怎么求100以内的素数? Visua 2005环境? 解决方案 http://www.51testing.com/html/25/237925-232093.html 求采纳,谢谢 解决方案二: 代码http://zhidao.baidu.com/link?url=Ou2UF57bXZE_XaBUkZN-00294GQSf2ZhahMHI988ZsvFqahXbREyAS7mn2f-vtw1D8bZuoFBgppfEgMD7mLQWwB

编程题-如何在C#中用math.sqrt实现求200以内的素数?

问题描述 如何在C#中用math.sqrt实现求200以内的素数? 不用函数,用嵌套循环.始终没想明白怎么写................... 解决方案 using System;public class Test{ public static void Main() { for (int i = 2; i < 200; i++){ bool isp = true; for (int j = 2; j <= Math.Sqrt((double)i); j++) { if (i % j ==

Ruby、PHP、Shell实现求50以内的素数_ruby专题

ruby求50之内的素数的方法,感觉对比PHP和SHELL方法是最简单的,但SHELL中可以利用factor命令,而PHP中没有求素数的对应函数的,需要自己设计算法,三种方式大家对比学习下,应该还有更优更简单的方法的. 复制代码 代码如下: #encoding:utf-8 #求50以内的素数(注意数字中..与...的区别)   for i in 2..50 #1默认不为素数,所以从1-50范围内被排除     f=true #起始假定每个数都是素数     for p in 2...i #比自身

GO语言求100以内的素数_Golang

本文实例讲述了GO语言筛选法求100以内的素数.分享给大家供大家参考.具体实现方法如下: 思路:找出一个非素数就把它挖掉,最后剩下就是素数. 下面就来欣赏一下go简洁的代码吧 目前不支持GO的代码插入,使用xml的代替一下. 复制代码 代码如下: package main import (     "fmt"     "math" ) func main() {     var i, j, n int     var a [101]int     for i = 1

java使用筛选法求n以内的素数示例(java求素数)_java

复制代码 代码如下: /** * @author jxqlovedn * 埃拉托斯特尼素数筛选法,请参考:http://zh.wikipedia.org/zh-cn/埃拉托斯特尼筛法 */public class AratosternyAlgorithm {  public static void getPrimes(int n) {  if(n < 2 || n > 1000000)   // 之所以限制最大值为100万,是因为JVM内存限制,当然有其他灵活方案可以绕过(比如位图法)   t

Ruby测试小代码[计算50以内的素数]

算法思想 判断某一个数,能不能被比他平方根小的素数整除. 首先看看代码 $arr = [] $arr[0] = 2 def add_prime(n) 3.step(n,2){|num| $arr <<num if is_prime?num } end def is_prime?(number) j=0 while $arr[j]*$arr[j]<=number return false if number % $arr[j] == 0 j += 1 end return true end

C++第11周项目3(6)——万以内可逆素数

课程首页地址:http://blog.csdn.net/sxhelijian/article/details/7910565 [项目3- 有趣的数字]先阅读例题,体会处理数字的一般方法,然后自行选题进行解决,掌握这种类型程序设计的一般方法. 任务:解决下面的问题(选做一道即算完成任务) (6)若一个素数的反序数仍为素数,则称为可逆素数.求10000以内的所有可逆素数. #include<iostream> #include<cmath> using namespace std; i

java求100以内的素数示例分享_java

复制代码 代码如下: package airthmatic; public class demo8 { /**  * 素数是指因数只有1和本身的数字  * @param arg  */ public static void main(String arg[]) {  for(int i=1;i<=100;i++)  {   if(find(i))    System.out.print(i+" ");  } }  /**  * 1-n个自然数中的素数  * @param n  *

求101-200以内的素数

素数就是除了它本身以及1之外不能被其他数整除 基本思路是,循环101-200之间的数字,让每一个数字都去循环除以2到它本身的数字,设定条件,这样一个循环后,总会取模为0,(任何数除以它本身都能整除),取模为0后进行判断,如果使它等于0的数是它本身,那么意味着除了2和它本身,不能被其他数整除,那么这个数就是素数. 代码如下: public class Sushu { public static void main(String[] args) { int count=0; for(int i=10