用筛法把要用到的素数求出来,存放到一个数组中备用.然后才对目标数进行质因数分解.OJ上的一道题 就是输入一个数进行质因数
来源:学生作业帮 编辑:大师作文网作业帮 分类:综合作业 时间:2024/09/30 19:29:00
用筛法把要用到的素数求出来,存放到一个数组中备用.然后才对目标数进行质因数分解.OJ上的一道题 就是输入一个数进行质因数分解.求好的算法呀.我的总是超时的.#include
#include
int main()
{
int a[70001],b[500];
int i,j,num,count=0,state=0;
for(i=2;i
#include
int main()
{
int a[70001],b[500];
int i,j,num,count=0,state=0;
for(i=2;i
筛选算法优化一下,用10内的素数筛选100内的素数,再用结果筛选10000内的,以此类推,用单链表省去数组往前挪的时间,在不懂我看看什么时间有空再帮你吧
再问: 大牛,能具体点吗?貌似很不错呀!!!!!(我刚用了你说的方法,没用到链表,因为看不懂,还是超时呀。 Sample Input 90 6 7 Sample Output 2 3 3 5 2 3 1 7 Hint 这题对很多初学者比较难一点。这里给一些提示吧:如果要代码的速度够快,不妨(用筛法)把要用到的素数求出来,存放到一个数组中备用。然后才对目标数进行质因数分解。
再答: 以前做的,我也不知道会不会超时,vc++ 6.0 编译通过 # include #include #include typedef struct node { int k; struct node *next; }linklist; linklist * init(linklist *l) { l=(linklist *)malloc(sizeof(linklist)); l->next=NULL; return l; } linklist * shaixuan(linklist *l,linklist **w,int low,int high) { linklist *p,*q;int k,i; for(i=low;ikk)==0) {k=1;break;} q=q->next; } if(k==1) continue; else { p=init(p); p->k=i; (*w)->next=p; (*w)=p; } } return l; } void main() { linklist *l,*w,*q; int num,c=2,high,count; l=init(l); w=l; l->k=2; while(1) { scanf("%d",&num); high=sqrt(num); if(ck0) { if(num%(q->k)==0) {printf("%d ",q->k);num=num/q->k;count++;} else q=q->next; } if(count==0) printf("%d %d",1,num); else printf("%d",num); } }
再问: 大牛,能具体点吗?貌似很不错呀!!!!!(我刚用了你说的方法,没用到链表,因为看不懂,还是超时呀。 Sample Input 90 6 7 Sample Output 2 3 3 5 2 3 1 7 Hint 这题对很多初学者比较难一点。这里给一些提示吧:如果要代码的速度够快,不妨(用筛法)把要用到的素数求出来,存放到一个数组中备用。然后才对目标数进行质因数分解。
再答: 以前做的,我也不知道会不会超时,vc++ 6.0 编译通过 # include #include #include typedef struct node { int k; struct node *next; }linklist; linklist * init(linklist *l) { l=(linklist *)malloc(sizeof(linklist)); l->next=NULL; return l; } linklist * shaixuan(linklist *l,linklist **w,int low,int high) { linklist *p,*q;int k,i; for(i=low;ikk)==0) {k=1;break;} q=q->next; } if(k==1) continue; else { p=init(p); p->k=i; (*w)->next=p; (*w)=p; } } return l; } void main() { linklist *l,*w,*q; int num,c=2,high,count; l=init(l); w=l; l->k=2; while(1) { scanf("%d",&num); high=sqrt(num); if(ck0) { if(num%(q->k)==0) {printf("%d ",q->k);num=num/q->k;count++;} else q=q->next; } if(count==0) printf("%d %d",1,num); else printf("%d",num); } }
用筛法把要用到的素数求出来,存放到一个数组中备用.然后才对目标数进行质因数分解.OJ上的一道题 就是输入一个数进行质因数
把一个数进行质因数分解后,它的因数是4个不同的质数,这个自然数最小是什么
如果把一个自然数分解质因数后,各个质因数的指数都是偶数,那么这个自然数就是完全平方数.
怎样用分解质因数来求出两个数的最小公倍数
把一个数分解质因数,这个数会有两个质因数二,一个质因数七,这个数是多少?
把一个数分解质因数,这个数含有2个质因数3,一个质因数5,这个数是?
把一个数分解质因数,这个数含有2个质因数2,一个质因数7,这个数( ).
一个数的最小倍数是52这个数是多少 把它分解成质因数是多少
一个数的最小公倍数是42,这个数是?把它分解质因数是?
一个数的最大约数是24,把这个数分解质因数是( )
一个数的最大约数是104,最小倍数室( ),把这个数分解质因数是( )
一个数的最大因数是90,把这个数分解质因数是【】