模板
教程
環境
性能
功能
管理
怎么計算出盡可能大的素數？
我的想法是要分配足夠大的內存！復雜點的可以把結果多次從一塊內存讀出(原因是結果太大了，沒有足夠大的內存一次儲存)。 devel : 在一臺電腦上做，需要重新寫個編譯器嗎？現在編譯器提供的數據類型的字節太小了。無法存放足夠大的結果。 libinary perl不是有
我的想法是要分配足夠大的內存！復雜點的可以把結果多次從一塊內存讀出(原因是結果太大了，沒有足夠大的內存一次儲存)。
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);
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。
能到這么多位？。。呵呵~~
要是內存小，是不是算得慢點？算不出估計不會，現在的內存都大與8M。
為什么要用：
for( tmp=((j-(j%2))/2);tmp>1;tmp-- )
一般應該是sqrt(j)，就算是按你的求一半，直接用j/2就可以了，
而且這里循環的方向用++比較好，
for( tmp=((j-(j%2))/2);tmp>1;tmp-- )
一般應該是sqrt(j)，就算是按你的求一半，直接用j/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;
}
}
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;
}
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)
內存占用大概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);
}
#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
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++大數運算方法 告訴你個地址，有C++的類，說是可以計算10000！值得研究。 http://www.cmjsoft.com/homepage/program/ /**************************************************************** * 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 :謝謝大家好熱心哦??！可惜我有些看不懂，還要慢慢看。。。。 |
- 評論列表（網友評論僅供網友表達個人看法，并不表明本站同意其觀點或證實其描述）
-
