模板
教程
环境
性能
功能
管理
怎么计算出尽可能大的素数？
我的想法是要分配足够大的内存！复杂点的可以把结果多次从一块内存读出(原因是结果太大了，没有足够大的内存一次储存)。 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 :谢谢大家好热心哦！！可惜我有些看不懂，还要慢慢看。。。。 |
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-
