我的想法是要分配足够大的内存！复杂点的可以把结果多次从一块内存读出(原因是结果太大了，没有足够大的内存一次储存)。 devel : 在一台电脑上做，需要重新写个编译器吗？现在编译器提供的数据类型的字节太小了。无法存放足够大的结果。 libinary perl不是有Math::BigInt吗 devel : 计算1至100间的素数，还有比这个程序更好的算法吗？
int
main(void)
{
unsigned j,tmp,count;
for(j=1;j<= 100;j++) {
count=0;
for( tmp=((j-(j%2))/2);tmp>1;tmp-- )
if( j % tmp ==0 ) {
count =1 ;
break;
}
if(count == 0 )
printf("%d ",j);
}
printf("\n");
return(0);
可算出1000位的素数的,只要计算机的内存足够大 unsigned long ----0~ 4294967295 能到这么多位？。。呵呵~~  要是内存小，是不是算得慢点？算不出估计不会，现在的内存都大与8M。
为什么要用：
for( tmp=((j-(j%2))/2);tmp>1;tmp-- )
一般应该是sqrt(j)，就算是按你的求一半，直接用j/2就可以了，
而且这里循环的方向用++比较好， sqrt()是开方的意思吗？
象你这样sqrt()不能通过。。。，不懂得怎么编程，
只好用perl也写了个。
sqrt()比((j-(j%2))/2)慢很多。。 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;
}
}
#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;
}
没研究过数论，只好搞点简单办法，把已经算出来的质数保存下来，这样就不用遍历所有小于sqrt(n)的数了，只要遍历一下小于sqrt(n)的质数就行了。
内存占用大概2.6M(一千万以内的质数)。
这个程序最大只能到max unsigned int(UINT_MAX)
#include
#include
#include
#include
unsigned int *m; /* 保存质数的数组 */
int num = 5; /* 当前质数的个数 */
int size = 1000; /* 当前m数组大小 */
const int addsize = 1000; /* m数组大小增量 */
void addm(unsigned int);
int ism(unsigned int);
int
main(void)
{
unsigned int n;
int i;
/* 为m分配size空间，初始化并打印num个元素 */
m = (unsigned int *)malloc(size * sizeof(unsigned int));
m[0] = 2U; m[1] = 3U; m[2] = 5U; m[3] = 7U; m[4] = 11U;
for(i = 0; i < num; i++)
printf("%u\n", m[i]);
/* 遍历n，如果n是质数就加入m并打印n */
/* UNIT_MAX计算时间太长，我没运行完就C-c了 */
/* 1千万打印到屏幕大概要1分钟，重定向到文件大概25秒 */
/* P3 500、 512M内存、 debian、 gcc 3.3 */
/* 另：增量我用n += 2试了一下，效果不明显 */
for(n = m[num - 1] + 2; n <= 10000000U/*UINT_MAX*/; n++){
if(ism(n)){
addm(n);
printf("%u\n", n);
}
}
free(m);
exit(0);
}
/* 将质数加入m，如果m空间不够就增加 */
void
addm(unsigned int n)
{
if(num == size){
size += addsize;
m = (unsigned int *)realloc(m, size * sizeof(unsigned int));
}
m[num] = n;
num++;
}
/* 判断是否是质数，用m里现存的质数整除n */
int
ism(unsigned int n)
{
int i, sn;
sn = sqrt(n);
for(i = 0; m[i] <= sn && i < num; i++)
if(n % m[i] == 0)
return(0);
return(1);
} 有两个数，分别是
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
syd168的程序看不懂，java? | 楼主其实是最大的难题应该是如何表示一个大整数吧？看各楼的帖子已经都有结果了，Perl/C/Java各显神通啊
有没有C++能实现一个大整数然后针对这个大整数类的重载操作符、普通数学库？
期待……
另，Python似乎天生有无限整数的特性，不知道有没有人愿意写写，这样的帖子很有趣…… C++大数运算方法
/****************************************************************
* 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::ostream;
//---------------------------------------------------------------------------
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
我原来看过debian里好像有C的无限精度整数库，不过忘了是什么名字了，C++的可以看看boost里面有没有 devel :谢谢大家好热心哦！！可惜我有些看不懂，还要慢慢看。。。。 |
|
