算法笔记(c++)--求一个数的所有质数因子 先贴题目: 这题不难,恶心在理解上面.最后看评论知道了怎么回事: 2*2*3*3*5=180 按照这逻辑的话应该输入的数由一系列质数相乘出来,所以每次找到一个质数就要更新下输入数.. 问题1: 没问题的话一瞬间都是这么想的.更新后重新来一遍for.重新探索一遍质数.但是仔细想想,题目要求从小到大,能2*3*2就一定能2*2*3,不如每次找到一个质数因子的时候,循环更新输入数. 解决如下 while(num%质数因子==0) num=num/质数因子.

php实现求一个数的质数因子 一.总结 一句话总结:这么简单的题目,还是把变量定义的位置和自增的位置写错. 1 <?php 2 $num=trim(fgets(STDIN)); 3 //如果$num大于1 4 $i=2; 5 while($num>1){ 6 while($num%$i==0){ 7 echo $i.' '; 8 $num=$num/$i; 9 } 10 $i++; 11 } 12 13 ?> 二.质数因子 题目描述 功能:输入一个正整数,按照从小到大的顺序输出它的所有质

对于这样的一个题目来说,出看来,可能会想到判断是否为质数,但其实并不需要. 只要按照从2开始遍历,只要遇到可以整除的就是想要的质数,理由是,如果遇到合数的话,那么在此之前一定会遇到这个合数的质因子,因此不会存在这种情况. 另外就是遍历的后边界,其实随着number的质因子被找到,因此number在逐渐减小,因此之后的遍历中是包括其自身的,因此需要 number+1 代码1:这样的方法尤其适用于大数字,否则会有很多无用的计算 def all_divisors(number): nb_list =

1. 求最小公倍数的算法: 最小公倍数  =  两个整数的乘积 /  最大公约数 所以我们首先要求出两个整数的最大公约数, 求两个数的最大公约数思路如下: 2. 求最大公约数算法: 1. 整数A对整数B进行取整, 余数用整数C来表示    举例: C = A % B 2. 如果C等于0,则B就是整数A和整数B的最大公约数 3. 如果C不等于0, 将B赋值给A, 将C赋值给B ,然后进行 1, 2 两步,直到余数为0, 则可以得知最大公约数 3. 程序代码实现如下: def fun(num1, n

一个数是不是质数,就是判断一个数除了1和它本身还有没有其他的约数,如果有则是合数,否则是质数.其实本质都是求公约数. 求公约数是什么思路呢,就是找比它小的数不断尝试,能被整除则是其约数,否则继续尝试,直到确定所有数都找遍.本着这个思路,求公约数的算法如下: public static List<long> GetGYS(long num) { ) }; ,num}; ,end=num/temp; while(temp<end){ ) list.Add(temp); temp++; end

Largest prime factor Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8976    Accepted Submission(s): 3191 Problem Description Everybody knows any number can be combined by the prime number. Now

D - Disjoint Set of Common Divisors Problem Statement Given are positive integers AA and BB. Let us choose some number of positive common divisors of AA and BB. Here, any two of the chosen divisors must be coprime. At most, how many divisors can we c

最近看到一个网站, 欧拉计划.挺好玩,都是一些算法题.这是本站:http://projecteuler.net/problems 这个是中文站:http://pe.spiritzhang.com/ 下面贴两个小脚本,低端玩具 1.找出一个数的所有因子: #encoding:utf-8 import math def yinzi(n): list_yinzi = [] if n <= 2: return list_yinzi for i in range(2, int(math.sqrt(n))

题目链接:http://lightoj.com/volume_showproblem.php?problem=1024 题意:给你n(2<=n<=1000)个数, 然后求n个数的最小公倍数,每个数的大小是1---10000;所以答案会很大,可能达到1000个4位数相乘:所以结果很大,将近4000位; 所以一定会涉及到高精度运算:同时我们也不能直接循环求最小公倍数:我们可以把一个数分解成多个质数相乘,然后找到所有数中,出现的质数最多的那个对应的次方,然后再把结果乘起来即可; 例如样例 4 5 6

解决的问题: 对于一个长度为n序列ai,求ai的最小公倍数 解析: 我们知道,如果求两个数a,b的LCM=a*b/gcd(a,b),多个数我们可以两两求LCM,再合并,这样会爆long long 所以这里我们用到了质因数分解法: 1.我们首先明确,他们的LCM是把每一个ai质因数分解之后,他们与其他ai的公共部分乘上自身特有的部分,即每一个质因子在ai中出现次数的最大值,是他们LCM的每一个质因子的出现次数t[i]. 2.所以我们将t[i]求解出即可相乘乘出LCM,这里只有乘法,可以取模. 实现

题意:给定n求,有n个因子的最小正整数. 题解:水题,zcr都会,我就不说什么了. 因数个数球求法应该知道,将m分解质因数,然后发现 a1^p1*a2^p2....an^pn这样一个式子, (1+p1)*(1+p2)*...=n,然后用小的质数填坑. #include <bits/stdc++.h> using namespace std; ,,,,,,,,,,,,,,,,}; ], res[], tmp[]; ], mn=DBL_MAX; void input() { scanf("

2154: 单身狗线下聚会 题目描述 马上就到七夕节了,单身狗们决定聚一聚.但是它们沉迷B站上的lo娘,他们每沉迷 ai 单身狗时间(这是它们专业计时)后就会休息 单身狗时间.它们想找到一个时间正好他们都在休息,然后聚在一起单身.但是,每一只单身都因为缺爱,所以非常讨厌52这个数字(它们非常喜欢12),所以它们最多沉迷51个单身狗时间. 单身狗们发现每过一段相同的单身狗时间 S ,它们就一定会全部聚在一起. 单身狗们想把这个作为加入单身狗聚会的考核,算不出来时间的单身狗就得加入它们.当然,作为一

输入一个不超过 10000 的正整数 n,求第n个质数 样例输入 10 样例输出 29 题目地址 #include<stdio.h> #include<math.h> int xxx(int n){ ; float a = sqrt(n); ;i <= a;i++){ ) flag = -; } ) ;//不是素数 else ; } int main(){ int n; scanf("%d",&n); ; while(n){ if(xxx(c))

除了分解质因数,还有另一种适用于求几个较小数的最大公约数.最小公倍数的方法 下面是数学证明及算法实现 令[a1,a2,..,an] 表示a1,a2,..,an的最小公倍数,(a1,a2,..,an)表示a1,a2,..,an的最大公约数,其中a1,a2,..,an为非负整数.对于两个数a,b,有[a,b]=ab/(a,b),因此两个数最小公倍数可以用其最大公约数计算.但对于多个数,并没有[a1,a2,..,an]=M/(a1,a2,..,an)成立,M为a1,a2,..,an的乘积.例如:[2,

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation. (Recall that the number of set bits an integer has is the number of 1s present when written in bin

题目: 质数因子 热度指数:5143 时间限制:1秒 空间限制:32768K 本题知识点: 排序 题目描述 功能:输入一个正整数,按照从小到大的顺序输出它的所有质数的因子(如180的质数因子为2 2 3 3 5 ) 最后一个数后面也要有空格 详细描述: 函数接口说明: public String getResult(long ulDataInput) 输入参数: long ulDataInput:输入的正整数 返回值: String 输入描述: 输入一个long型整数 输出描述: 按照从小到大的

质数的概念: 简单的来说就是一个数从2开始取模到(求余数)自身的值,如果取模后余数一直不等于0那么这个数就是质数(素数). 如 7     7%2    7%3    7%4    7%5   7%6  余数一直都不等于0    一直到7%7余数才为0:所以7是质数: 如 8   8%2余数直接为0:所以8不是质数: 如 9  9%2   9%3余数为0:所以8也不是质数: 下面直接上代码: package pkg1;//包名public class Test{//类名(注!该类名必须与文件名一

题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=200 200. Cracking RSA time limit per test: 0.25 sec.memory limit per test: 65536 KB input: standardoutput: standard The following problem is somehow related to the final stage of many famous intege

//这是求一个数的质因数,例如:12=2*2*3 其中2,3都是质数.function primeArray(n, array) { array = new Array(); for (var i = 2; i < n; i++) { //是否为质数 if (isPrime(i)) { var temp_R = n % i;//余数 var temp_c = n / i;//商 //是否整除 if (temp_R == 0) { // array[array.length] = i; array

我的思路是这样的:比如12和16这两个数.先理解一下概念,什么叫最大公约数.就是12有很多个因数,16也有很多个因数,这两堆因数中有一些重合的因数,在这些重合的因数中找到那个最大的.那么最大公约数一定是两个数的公约数,且最大公约数一定再12的因数中寻找的.OK,我们先对12求除所有的因数,那么需要一个循环,在这个循环中每次拿到12的一个因数,看它是不是16的一个因数,如果是,那么说明这个因数就是12和16的一个公因数,暂时把最大公约数设置为这个公因数,然后进行下次循环,如果能找到12和16的又一