怎么计算出尽可能大的素数？

devel

最初由 libinary 发表
为什么要用：
for( tmp=((j-(j%2))/2);tmp>1;tmp-- )
一般应该是sqrt(j)，就算是按你的求一半，直接用j/2就可以了，
而且这里循环的方向用++比较好，

sqrt()是开方的意思吗？
象你这样sqrt()不能通过。。。，不懂得怎么编程，
只好用perl也写了个。
sqrt()比((j-(j%2))/2)慢很多。。
:sorry 我说话没有注意

syd168

[PHP]import java.math.*;
import java.io.*;
class test{
  public static void main(String arg[]) throws IOException{
   BigInteger i=new BigInteger("1");
   String str;
   byte bs[];
   File f=new File("/root/temp/aa.txt");
   FileWriter fo=new FileWriter(f);
   fo.write("2");
   while(true){
     i=i.add(new BigInteger("2"));
     if(odd(i))//{fo.write(i.toString()+" ");fo.flush();}
      System.out.print(i.toString()+"  ");
     if((i.toString()).length()>4)break;
   }
   fo.close();
  }
  static boolean odd(BigInteger k){
    BigInteger j,b;
    j=new BigInteger("1");
    b=k.divide(new BigInteger("2"));
    //System.out.println();
    //System.out.print(k.toString()+"=");
    while(true){
      //System.out.print(j.toString()+" ");
      j=j.add(BigInteger.ONE);
      if((k.remainder(j)).compareTo(BigInteger.ZERO)==0)break;
      if(j.compareTo(b)>0)break;
    }
    if(j.compareTo(b)>0) return true;
    else return false;
  }
}[/PHP]

深空

[php]
#include "math.h"
int IsPrime(unsigned x);
main()
{
unsigned a;
int j;
printf("\nPrime in 100-200 is:\n");
for(j=0,a=100;a<=200;a++)
   {
    if(IsPrime(a))
     {
      printf("%8u",a);j++;
      if(j%5==0) printf("\n");
      }
   }
}
int IsPrime(unsigned x)
{
  unsigned a,b ;
  a=sqrt(x);
  for(b=2;b<=a;b++)
  if(x%b==0) return 0;
  return 1;
}[/php]

libinary

没研究过数论，只好搞点简单办法，把已经算出来的质数保存下来，这样就不用遍历所有小于sqrt(n)的数了，只要遍历一下小于sqrt(n)的质数就行了。
内存占用大概2.6M(一千万以内的质数)。
这个程序最大只能到max unsigned int(UINT_MAX)

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <limits.h>
   
5. #include <math.h>
   
6. 
   
7. unsigned int *m; /* 保存质数的数组 */
   
8. int num = 5;     /* 当前质数的个数 */
   
9. int size = 1000; /* 当前m数组大小 */
   
10. const int addsize = 1000; /* m数组大小增量 */
    
11. 
    
12. void addm(unsigned int);
    
13. int ism(unsigned int);
    
14. 
    
15. int
    
16. main(void)
    
17. {
    
18.   unsigned int n;
    
19.   int i;
    
20. 
    
21.   /* 为m分配size空间，初始化并打印num个元素 */
    
22.   m = (unsigned int *)malloc(size * sizeof(unsigned int));
    
23.   m[0] = 2U; m[1] = 3U; m[2] = 5U; m[3] = 7U; m[4] = 11U;
    
24.   for(i = 0; i < num; i++)
    
25.     printf("%u\n", m[i]);
    
26. 
    
27.   /* 遍历n，如果n是质数就加入m并打印n */
    
28.   /* UNIT_MAX计算时间太长，我没运行完就C-c了 */
    
29.   /* 1千万打印到屏幕大概要1分钟，重定向到文件大概25秒 */
    
30.   /* P3 500、 512M内存、 debian、 gcc 3.3 */
    
31.   /* 另：增量我用n += 2试了一下，效果不明显 */
    
32.   for(n = m[num - 1] + 2; n <= 10000000U/*UINT_MAX*/; n++){
    
33.     if(ism(n)){
    
34.       addm(n);
    
35.       printf("%u\n", n);
    
36.     }
    
37.   }
    
38.   free(m);
    
39. 
    
40.   exit(0);
    
41. }
    
42. 
    
43. /* 将质数加入m，如果m空间不够就增加 */
    
44. void
    
45. addm(unsigned int n)
    
46. {
    
47.   if(num == size){
    
48.     size += addsize;
    
49.     m = (unsigned int *)realloc(m, size * sizeof(unsigned int));
    
50.   }
    
51.   m[num] = n;
    
52.   num++;
    
53. }
    
54. 
    
55. /* 判断是否是质数，用m里现存的质数整除n */
    
56. int
    
57. ism(unsigned int n)
    
58. {
    
59.   int i, sn;
    
60. 
    
61.   sn = sqrt(n);
    
62.   for(i = 0; m[i] <= sn && i < num; i++)
    
63.     if(n % m[i] == 0)
    
64.       return(0);
    
65.   return(1);
    
66. }
    

复制代码

syd168

[PHP]有两个数，分别是

a=53495833453546435464565364464545465655456544565456346334553345453345786786453453453454598345983459834589345738495738945783943495833453546435464534958334535464354645349583345354643546453495833453543495833453546435464534958334535464354645349583345354643546456435464534958334535464354645578934

b=53456867867863495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535463495833453546435464534958334535464354645349583345354643546454354645

他们的乘积是多少？
程序如下：
类似，就可以计算100位甚至更多位的质数，我看了看，要计算100位的素数可能需要几天时间

import java.math.*;
import java.io.*;
class test1{
  public static void main(String arg[]) throws IOException{
    BigInteger a,b,c;
    a=new BigInteger("53495833453546435464565364464545465655456544565456346334553345453345786786453453453454598345983459834589345738495738945783943495833453546435464534958334535464354645349583345354643546453495833453543495833453546435464534958334535464354645349583345354643546456435464534958334535464354645578934");
    b=new BigInteger("53456867867863495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535464354645349583345354643546453495833453546435464534958334535463495833453546435464534958334535464354645349583345354643546454354645");
    c=a.multiply(b);
  System.out.print(c.toString());
  }

}
结果是：

2859719700407463512472375639436620183805313967940900968210967716218455605011805522565539073658830569132370459898385027707435330527666094536175361588945018324191941685102124923120221297543147996629828088312053446872660779988616507356056518697593406008538586065079967339832704628616723685731390779629837724572324821894718325466874161112611901526450346334268663484049255867388807238337508189254164510466323037135539708606291662241544045953164756030464848351518774044385142562435059005279607187155842600533234371912976675056819434933622486603169413855118418628875016063141806081377048430[/PHP]

devel

syd168的程序看不懂，java?

feng_ye

楼主其实是最大的难题应该是如何表示一个大整数吧？看各楼的帖子已经都有结果了，Perl/C/Java各显神通啊

有没有C++能实现一个大整数然后针对这个大整数类的重载操作符、普通数学库？

期待……

另，Python似乎天生有无限整数的特性，不知道有没有人愿意写写，这样的帖子很有趣……

syd168

告诉你个地址，有C++的类，说是可以计算10000！值得研究。
http://www.cmjsoft.com/homepage/program/

syd168

[PHP]/****************************************************************
*             Cmjint class created by airsupply 2001.12.12
*                   magiclink.xiloo.com
*               
*               
*****************************************************************
*        Cmjint class is a super limitless int
*        you can use it to caculate a huge number
*        Exsample:
*
*        Cmjint i,x;
*         i="-123413141431342341";         //can init as char*  as long as you can
*         x=123123;                                //can init as long
*         i+=x;
*         i*=x;
*         i.Print();
*         printf("%s",i.Str());
*        if (i>x) cout <<i;                //as easy as int
***************************************************************/
//---------------------------------------------------------------------------
#ifndef CLONGH
#define CLONGH
//---------------------------------------------------------------------------
#include <iostream>
using std::cout;
using std::ios;
using std:stream;
//---------------------------------------------------------------------------
typedef long typeint;//user type
typedef struct Unitint
{
typeint i;
Unitint * left;
Unitint * right;
Unitint():left(NULL),right(NULL),i(0){}
}* Punitint;
enum emLR{emLeft,emRight};
//---------------------------------------------------------------------------
// class
//---------------------------------------------------------------------------
class Cmjint
{
private:
friend ostream &  operator <<(ostream &,const Cmjint &);
static void _Mul8(Cmjint &,const Cmjint &,const typeint &);                    //need by mul
static void _moveleft_onebit(Cmjint & ,  short ) ;                            //need by mul
static bool _getsfromhead(const Cmjint&,char *,short ) ;                      //need by div
static void _getnumfromright(const Cmjint & ,const short&,short & ) ;         //need by div

void Allocate(Punitint & pnew,emLR linkLR);
void Constructor(){bit=plus=1;data=Ldata=Rdata=NULL;str=NULL;} //init private data
void Deletezero();
Punitint data;
Punitint Ldata; //left bounds
Punitint Rdata; //right bounds
short bit;
char * str;
static const short   __B;
static const typeint __base;
static const short   __h_base;  //half of base
static const char    _NUM[];
public:
      Cmjint()                  {Constructor();data=new Unitint;Ldata=data;Rdata=data;}
      Cmjint(const Cmjint& lint){Constructor();*this=lint;}
      Cmjint(const typeint &i)   {Constructor();*this=i;    }
      Cmjint(const char * str)     {Constructor();*this=str; }
      ~Cmjint();
      //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      Cmjint& operator+=( const Cmjint & );
      Cmjint& operator-=(const Cmjint & );
      Cmjint& operator*=( const Cmjint & );
      Cmjint& operator/=( const Cmjint & );
      Cmjint& operator%=( const Cmjint & );
      Cmjint operator++(int);
      Cmjint operator--(int);
      Cmjint& operator++();
      Cmjint& operator--();
      Cmjint operator+(const Cmjint& )        const;
      Cmjint operator-(const Cmjint & )        const;
      Cmjint operator*(const Cmjint& )        const;
      Cmjint operator/(const Cmjint& )        const;
      Cmjint operator%(const Cmjint& )        const;
      Cmjint operator-();
      Cmjint& operator=( const typeint & ) ;
      Cmjint& operator=( const Cmjint & );
      Cmjint& operator=(const char *  );
      bool operator>( const Cmjint & )        const;
      bool operator>=( const Cmjint & )        const;
      bool operator<=( const Cmjint & )        const;
      bool operator<( const Cmjint & )        const;
      bool operator==( const Cmjint & )        const;
      bool operator!=( const Cmjint & )        const;
      //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      bool  plus;
      void Print();         
      int Length()const;     //number bits
      void Clear();          //reset data to 0
      char * c_str();
};
extern Cmjint operator+(const typeint &tthis,const Cmjint &sthis);

extern Cmjint operator-(const typeint &tthis,const Cmjint &sthis);

extern Cmjint operator*(const typeint &tthis,const Cmjint &sthis);

extern Cmjint operator/(const typeint &tthis,const Cmjint &sthis);

extern Cmjint operator%(const typeint &tthis,const Cmjint &sthis);

//~~~~~~~~
extern Cmjint operator+(const char * tthis,const Cmjint &sthis);

extern Cmjint operator-(const char * tthis,const Cmjint &sthis);

extern Cmjint operator*(const char * tthis,const Cmjint &sthis);

extern Cmjint operator/(const char * tthis,const Cmjint &sthis);

extern Cmjint operator%(const char * tthis,const Cmjint &sthis);

#endif[/PHP]

libinary

我原来看过debian里好像有C的无限精度整数库，不过忘了是什么名字了，C++的可以看看boost里面有没有