[编程题]质数因子
import java.util.*;
import java.io.*;
public class Main {
/*
既是质数又是因子
*/
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
while ((str = br.readLine()) != null) {
long n = Long.parseLong(str);
String res = getStr(n);
System.out.println(res);
}
}
// 获取输出格式
public static String getStr(long num) {
String ret = "";
for(int i = 2; i*i <= num; i++) { // 求质数
while (num % i == 0) {// 求因子
ret += i + " ";
num /= i;
}
}
if (num != 1) ret += num + " ";
return ret;
}
}
import java.io.*;
public class Main {
/*
既是质数又是因子
*/
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
while ((str = br.readLine()) != null) {
long n = Long.parseLong(str);
String res = getStr(n);
System.out.println(res);
}
}
// 获取输出格式
public static String getStr(long num) {
String ret = "";
for(int i = 2; i*i <= num; i++) { // 求质数
while (num % i == 0) {// 求因子
ret += i + " ";
num /= i;
}
}
if (num != 1) ret += num + " ";
return ret;
}
}
发表于 2021-07-16 17:29:51
回复(0)
a = int(input())
Outlist = []
for i in range(2, a // 2 + 1):
#for i in range(2, int(math.sqrt(a)) + 1):
while a % i == 0:
a = a / i
Outlist.append(i)
Outlist = []
for i in range(2, a // 2 + 1):
#for i in range(2, int(math.sqrt(a)) + 1):
while a % i == 0:
a = a / i
Outlist.append(i)
print(" ".join(map(str, Outlist)) + " " if Outlist else str(a) + " ")
此题的关键是找出所有质数因子，而且每个质数因子可能有多个
发表于 2019-08-31 10:31:30
回复(0)
高票答案没有忽略了题目要求的字符串转化...
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int hex2dec(string s);
string getResult(long ulDataInput);
string myitoa(long a);
int main(){
long str;
string a;
while (cin >> str)
cout << getResult(str);
return 0;
}
string getResult(long ulDataInput)
{
string str = "";
char a[100];
for (int i = 2; i <= ulDataInput; )
{
if ((ulDataInput%i) == 0)
{
ulDataInput /= i;
str += myitoa(i);
str += " ";
}
else
i++;
}
return str;
}
string myitoa(long a)
{
string str="";
vector<int> nums_r;
vector<int> nums;
while (a)
{
nums_r.push_back(a % 10);
a /= 10;
}
for (auto i = nums_r.end()-1;i>nums_r.begin();i--)
nums.push_back(*i);
nums.push_back(nums_r[0]);
for (int i : nums)
{
switch (i)
{
case 0: str += "0"; break;
case 1: str += "1"; break;
case 2: str += "2"; break;
case 3: str += "3"; break;
case 4: str += "4"; break;
case 5: str += "5"; break;
case 6: str += "6"; break;
case 7: str += "7"; break;
case 8: str += "8"; break;
case 9: str += "9"; break;
default:
break;
}
}
return str;
}
#include <string>
#include <vector>
using namespace std;
int hex2dec(string s);
string getResult(long ulDataInput);
string myitoa(long a);
int main(){
long str;
string a;
while (cin >> str)
cout << getResult(str);
return 0;
}
string getResult(long ulDataInput)
{
string str = "";
char a[100];
for (int i = 2; i <= ulDataInput; )
{
if ((ulDataInput%i) == 0)
{
ulDataInput /= i;
str += myitoa(i);
str += " ";
}
else
i++;
}
return str;
}
string myitoa(long a)
{
string str="";
vector<int> nums_r;
vector<int> nums;
while (a)
{
nums_r.push_back(a % 10);
a /= 10;
}
for (auto i = nums_r.end()-1;i>nums_r.begin();i--)
nums.push_back(*i);
nums.push_back(nums_r[0]);
for (int i : nums)
{
switch (i)
{
case 0: str += "0"; break;
case 1: str += "1"; break;
case 2: str += "2"; break;
case 3: str += "3"; break;
case 4: str += "4"; break;
case 5: str += "5"; break;
case 6: str += "6"; break;
case 7: str += "7"; break;
case 8: str += "8"; break;
case 9: str += "9"; break;
default:
break;
}
}
return str;
}
发表于 2018-07-07 21:30:52
回复(0)
//package com.gulamjan.t021.华为质数因子;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
long n = in.nextLong();
System.out.println(getPrimeString(n));
}
in.close();
}
//判断 n 是否是个质数
public static boolean isPrimeNumber(long n) {
boolean flag = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
flag = false;
break;
}
}
return flag;
}
//获取符合要求的因子字符串
public static String getPrimeString(long n) {
long temp = n;
String string = "";
for (int i = 2; i <= temp; i++) {
if (isPrimeNumber(i)) {
while(n % i == 0){
string += i+" ";
n = n / i;
}
}
}
return string;
}
}
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
long n = in.nextLong();
System.out.println(getPrimeString(n));
}
in.close();
}
//判断 n 是否是个质数
public static boolean isPrimeNumber(long n) {
boolean flag = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
flag = false;
break;
}
}
return flag;
}
//获取符合要求的因子字符串
public static String getPrimeString(long n) {
long temp = n;
String string = "";
for (int i = 2; i <= temp; i++) {
if (isPrimeNumber(i)) {
while(n % i == 0){
string += i+" ";
n = n / i;
}
}
}
return string;
}
}
发表于 2017-10-05 16:42:04
回复(0)
#include <stdio.h>
#include <string.h>
#define N 100
int main()
{ long i; int j; long n; char over; long devisor[N]; scanf("%ld", &n); j = 0; while(1){ over = 1; for(i=2 ; i<=(n+1)/2 ; i++){ if(n%i == 0){ devisor[j++] = i; n /= i; over = 0; break; } } if(over) break; } for(i=0 ; i<j ; i++){ printf("%ld ", devisor[i]); } printf("%ld \n", n); }
编辑于 2017-09-17 10:54:27
回复(0)
def a(m):
k =0
for i in range(2,m):
if m%i ==0:
k+=1
break
if k >0:
return i,m//i
else:
return m
def b(n):
t =a(n)
if n ==t:
print(n,end=' ')
else:
for i in t:
b(i)
b(int(input()))
k =0
for i in range(2,m):
if m%i ==0:
k+=1
break
if k >0:
return i,m//i
else:
return m
def b(n):
t =a(n)
if n ==t:
print(n,end=' ')
else:
for i in t:
b(i)
b(int(input()))
发表于 2022-06-08 15:21:26
回复(0)
import java.util.*;
public class Main{
public static void getPrimer(long num){
long sqrNum=(long)Math.sqrt(num);
for(int i=2;i<=sqrNum;i++){
if(num%i==0){
System.out.print(i+" ");
getPrimer(num/i);
break;
}
if(i==sqrNum){
System.out.print(num+" ");
}
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
long num=in.nextLong();
getPrimer(num);
}
public class Main{
public static void getPrimer(long num){
long sqrNum=(long)Math.sqrt(num);
for(int i=2;i<=sqrNum;i++){
if(num%i==0){
System.out.print(i+" ");
getPrimer(num/i);
break;
}
if(i==sqrNum){
System.out.print(num+" ");
}
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
long num=in.nextLong();
getPrimer(num);
}
}
取根号num作为比较总次数来避免大质数超时，递归思想
发表于 2022-01-08 13:53:00
回复(1)
好多人没明白这个问题的意思，其实就是让你把输入的整数因式分解，只不过因子必须都是质数
例如：180 = 2 * 2 * 3 * 3 * 5；90 = 2 * 3 * 3 * 5；而不是找出所有的质数因子
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
long number = 0;
while(scanner.hasNextLong())
{
number = scanner.nextLong();
isPrimerFactors(number);
}
}
private static void isPrimerFactors(long num)
{
long number = num;
while(number != 1)
{
for(int i = 2; i <= number ;i++)
{
if(number % i == 0)
{
number /= i;
System.out.print(i + " ");
break;
}
}
}
}
}
发表于 2016-07-27 10:25:09
回复(51)
num = int(input()) fac = [] if num>=2: #如果输入为1，则没有质因子。所以只需要考虑输入大于等于2. i=2; while i<= int(num**0.5)+1: # 对于输入num，我们只需要搜索至m，使得m^2>=num。再往后仍无质因子说明num本身就是最后一个质因子。 if num%i == 0: fac.append(i) num = num/i # 找到一个质因子后即可减小num。 else: i+=1 fac.append(int(num)) for i in fac: print(i,end=" ")
发表于 2021-06-18 12:49:22
回复(0)
1. 需要优化下算法复杂度，不然计算时会超时
2. 判断一个数是否是质数：优化--》是否是6的倍数的相邻数（除了2、3），如果不是那一定不是质数，
然后判断从5开始累加（一次累加6），直到概述的平方根为止，如果没有因数，即为质数
using System;
class Solution
{
static void Main()
{
long param =long.Parse(Console.ReadLine());
if(param == 1) Console.Write("");
long temp = param ;
for(long k = 2;k<= temp;k++)
{
if(IsPrime(k))
{
while(temp % k== 0)
{
temp = temp/k;
Console.Write(k + " ");
}
}
}
//if(IsPrime(param)) Console.WriteLine(param + " ");
}
public static bool IsPrime(long num)
{
if(num == 2 || num == 3) return true;
if(num %6 != 1 && num % 6 != 5) return false;
for(long i = 5;i <= Math.Sqrt(num) ;i+=6)
{
if(num % i == 0 && num %(i + 2) == 0) return false;
}
return true;
}
}
发表于 2019-12-18 12:36:23
回复(1)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
long num = scanner.nextLong();
List<Long> factors = new ArrayList<>();
while(num>0&&!IsPrimer(num)){
long i =2;
while(i*i<num){
if(num%i == 0){
factors.add(i);
num = num/i;
break;
}
i++;
}
}
factors.add(num);
if(factors.size() == 0){
;
}else{
for(long i : factors){
System.out.print(i + " ");
}
}
System.out.println();
}
}
public static boolean IsPrimer(long a){
boolean flag = true;
for(int i =2; i<=Math.sqrt(a);i++){
if(a%i == 0){
flag = false;
return flag;
}
}
return flag;
}
}
发表于 2017-04-04 11:14:03
回复(0)
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
bool isPrime(int n)
{
int flag = false;
for (int i = 2; i <= sqrt(n); i++)
{
if (n%i == 0)
return flag;
}
flag = true;
return flag;
}
int main()
{
int n;
while (cin >> n)
{
int m = n;
while (m>1)
{
for (int i = 2; i <= m; i++)
{
if ((m%i == 0) && isPrime(i))
{
cout << i << " ";
m = m / i;
break;
}
}
}
}
return 0;
}
发表于 2016-03-09 16:12:03
回复(0)
再简洁不过的C++的方式，共三种方法：
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long int input;
//方法一
//while (cin >> input)
//{
// while (input != 1)
// {
// for (int i = 2; i <= input; i++)
// {
// if (input % i == 0)
// {
// input /= i;
// cout << i << ' ';
// break; //只要能被i整除，i总是从2开始
// }
// }
// }
//}
//方法二
//while (cin >> input)
//{
// for (int i = 2; i <= input; i++)
// {
// //只要能被i整除，i总是从2开始
// if (input%i == 0)
// {
// input /= i;
// cout << i << " ";
// i = 1;//经i++之后 i又变为2开始
// }
// }
//}
//方法三
while (cin >> input)
{
for (int a = 2; a<= sqrt(input); a++)
{
//此处是while,把a整除结束才可加1
while (input%a == 0)
{
cout << a << ' ';
input = input / a;
}
}
if (input>1) cout << input << ' ';
}
//system("pause");
return 0;
}
编辑于 2016-07-04 21:47:33
回复(18)
#一个整数x的质因子的求法： # step1:在2~x^0.5上,从2开始除x,如果能整除,记录下这个除数,然后用商去继续进行上述的操作,直到商为1； # step2:如果除不进，除数加一。如果一直加一，除数大于x^0.5,则说明x的质因子只有它本身。 # 被除数 ÷ 除数=商···余数 def FindPrimeNumber(num): lst = [] i = 2 #从2开始除num while num != 1: #商不等1时 if num % i == 0: lst.append(i) #如果能整除,记录下这个除数i num //= i #更新num,num = 商 else: #如果num除以i除不尽 if i>int(num**0.5): #当i大于根号num时，说明num的质因子只有它本身,此时结束循环 lst.append(num) break else: i+=1 #除数i+1 for item in lst: print(item,end=' ') if __name__=='__main__': x = int(input()) FindPrimeNumber(x)
发表于 2021-09-06 00:09:29
回复(3)
问题信息
通过挑战的用户
查看代码-
2023-03-07 20:23:25 -
2023-02-02 23:55:15
-
2023-01-24 12:08:15 -
2023-01-07 14:37:29 -
2022-12-02 16:24:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
