知识点
质数:大于1的整数中,只能被1和本身整除,不能被其他数整除就叫做质数,也可以叫做素数
举例:2,3,5,7,11,13......
合数:大于1的整数中,除了1和本身整除外,还能被其他数整除,就叫做合数,与质数相对,最小的合数是4
举例:4,6,8,9,10.....
因数:整数a可以整除b,那么b就是a的因数,也可以叫做约数
举例:下面两种表现形式都是可以的
4 / 2 = 0,2是4的因数,
2 * 2 = 4,2是4的因数
质因数:可以整除正整数的质数,可以理解为一个数既是因数,又是质数
举例:12 = 2 * 2 * 3,2和3就是12的质因数,3 * 4 = 12,因为4不是质数,所以也不是质因数
算法详解
这个题的算法思想是如果一个数是合数,那就把这个合数不断的除以一个最小质因数,直到不是这个质因数的倍数,再用这个数不断的除以下一个质因数,直到为1为止
如果是质数,直接输出本身 + 1即可
举例:180 = 2 * 2 * 3 * 3 * 5 = 2^2^ * 3 ^2^ * 5 ^1^
因为180是合数,2是最小的质因数,所以用180不断的除以2,直到除不了了为止,也就是45
因为45是合数,3是下一个最小的质因子,所以用45不断的除以3,也就是5
因为5是质数,i等于4,4 >= 5/4,所以直接输出5 + ” ” + 1;
问题详解
1:if (x % i == 0)
为什么这里的i一定是质因数
首先要明白一点,如果一个数是质因数,那么这个数既是一个因数,又是一个质数;所以我只要证明了这两点,就可以说是质因数
//要在优化之前的代码中试验,因为如果是优化之后的,会直接跳出循环
for(int i = 2; i <= x; i ++)
{
if(x % i == 0)
{
int s = 0;
while(x % i == 0)
{
x /= i;
s ++;
}
}
}
1:如果x % i == 0
,那么i一定是因数,根据概念就可以知道了
2:一个大于1的数不是质数就是合数,合数一定是质数的乘积;这句话一定是正确的,大家可以拿着实际例子去试一试
如果i是一个合数的话,那么会自动的跳出循环,因为除以质数都除不尽了,更别说合数了,所以i一定是一个质数
举例:x如果连2都除不尽了,那么4就一定也除不尽(4是最小的合数)
java代码
import java.util.Scanner;
public class Main{
static int N = 110;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
while(n-- > 0)
{
int x = in.nextInt();
divide(x);
}
}
private static void divide(int x)
{
for(int i = 2; i <= x / i; i ++) //这里和质数题是一样的
{
if(x % i == 0) //如果x是合数,那就进行拆分
{
int s = 0; //s代表质因数出现的次数
while(x % i == 0)
{
x /= i;
s ++;
}
System.out.println(i + " " + s);
}
}
if(x > 1) System.out.println(x + " " + 1); //如果x是质数,那么就输出本身 和 1
System.out.println();
}
}
棒!