我正在研究一个问题，给定一个整数N，我需要找到它的所有除数并按顺序打印它们，使得对于列表中的任意两个连续除数，以下条件成立：
较大的除数除以较小的除数会得到质数。
例如，对于N = 12，除数的一个可能有效排序是：
1 2 4 12 6 3
按此顺序：
- 2/1=2（素数）
- 4/2=2（素数）
- 12/4=3（素数）
- 12/6=2（素数）
- 6/3=2（素数）
如果有多个有效的解决方案，其中任何一个都可以。
我编写了一个解决方案，可以找到N的所有除数并对其进行排序，但我很难弄清楚如何根据这个素数商条件对它们进行排序。例如，对于N = 12，我可以实现输出1 2 4 12 6 3，但我无法为N的其他值一致地生成这样的序列。
我的问题：
我该如何解决这个问题，并为满足素数商条件的任何整数N构建正确的除数序列？任何见解或建议都将不胜感激！
附加背景：我正在使用 C++ 来解决问题，并且对于较大的N值，性能是一个问题。
我编写了一个解决方案，可以找到N的所有除数并对其进行排序，但我很难弄清楚如何根据这个素数商条件对它们进行排序。下面是我当前代码的一个最小示例：
输入：
2
12
100
输出：
1 2 4 12 6 3
1 2 4 20 10 5 25 50 100
#include<bits/stdc++.h>
using namespace std;
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MOD 1000000007
#define endl "\n"
const int N = 1e3 + 7;
int32_t main() {
optimize();
int t;
cin >> t; // Read number of test cases
while (t--) {
vector<int> v, ans;
int n;
cin >> n; // Read the integer N
// Find all divisors of n
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
if (j == n) {
v.push_back(i);
}
}
}
// Attempt to build the sequence of divisors (incomplete logic)
// You need to implement the logic here to order the divisors based on the prime quotient condition
// Print the divisors for now
for (int val : v) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
18
最佳答案
2
找到一个素因数及其指数。例如，对于 N=36，找到 2^2。除以它，得到 N=9。递归求解，得到例如序列1 3 9。现在通过上下移动合并 2^2，并在中间乘以 2：
(1 3 9) (18 6 2) (4 12 36)
Python实现：
def divs(n, i=2):
if n == 1:
return [1]
while i * i <= n:
e = 0
while not n % i:
n //= i
e += 1
if e:
ds = divs(n, i+1)
result = ds[:]
while e:
ds.reverse()
ds = [d * i for d in ds]
result += ds
e -= 1
return result
i += 1
return [1, n]
print(*divs(12))
print(*divs(36))
输出（）：
1 3 6 2 4 12
1 3 9 18 6 2 4 12 36
更直接的自下而上的方式：
def divs(n):
result = [1]
i = 2
while n > 1:
if i * i > n:
i = n
ds = result
while not n % i:
n //= i
ds = [d * i for d in reversed(ds)]
result += ds
i += 1
return result
print(*divs(12))
print(*divs(36))
输出（）：
1 2 4 12 6 3
1 2 4 12 6 3 9 18 36
3
-
1我喜欢这个——类似于格雷码构造：
– -
好的，但是问题标签是 C++。
– -
@Wyck 但我不是 C++ 专家，问题是“我该如何解决这个问题，并为满足素数商条件的任何整数 N 构建正确的除数序列？任何见解或建议都将不胜感激！”。我的第一部分回答了这个问题。实现已经是一个奖励。
–
|
好吧，我用一些示例代码扩展了我之前的评论。这更多的是为了让它工作而不是让它达到最佳状态，所以欢迎提出建设性的批评。对于下面的 DFS… 好吧，我不是计算机科学家。
找到所有除数。将它们写为 GRAPH 的节点。如果较大/较小为素数，则节点相连。遍历该图（通过 DFS），访问每个节点一次。
（请注意，在我的代码中，节点是已排序除数的索引，而不是除数本身。）
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
//======================================================================
bool isPrime( int n ) // Test primality
{
if ( n < 2 ) return false;
if ( n % 2 == 0 ) return n == 2;
int imax = sqrt( n + 0.5 );
for ( int i = 3; i <= imax; i += 2 )
{
if ( n % i == 0 ) return false;
}
return true;
}
//======================================================================
vector<int> getDivisors( int n ) // Find all divisors (including 1 and n)
{
vector<int> divisors = { 1 };
if ( n <= 1 ) return divisors;
divisors.push_back( n );
int imax = sqrt( n + 0.5 ); // proper divisors usually come in pairs
for ( int i = 2; i <= imax; i++ )
{
if ( n % i == 0 )
{
divisors.push_back( i );
divisors.push_back( n / i );
}
}
if ( imax * imax == n ) divisors.pop_back(); // don't double count
sort( divisors.begin(), divisors.end() );
return divisors;
}
//======================================================================
bool DFS( int test, vector<int> &sequence, const vector<vector<int>> &connections, vector<bool> &visited )
{
if ( visited[test] ) return false; // already used
sequence.push_back( test ); visited[test] = true; // add index to sequence
if ( sequence.size() == connections.size() ) return true; // finished successfully
for ( int next : connections[test] ) // try each node connected to test
{
if ( DFS( next, sequence, connections, visited ) ) return true;
}
sequence.pop_back(); visited[test] = false;
return false;
}
//======================================================================
int main()
{
int N;
cout << "Enter N: "; cin >> N;
vector<int> divisors = getDivisors( N ); // the collection of divisors
int numDivisors = divisors.size();
// Set up "connections"
vector<vector<int>> connections(numDivisors); // for each node (an index), the indices that it is connected to
for ( int i = 0; i < numDivisors; i++ )
{
for ( int j = 0; j < numDivisors; j++ )
{
int a = divisors[i], b = divisors[j];
if ( a > b && a % b == 0 && isPrime( a / b ) )
{
connections[i].push_back( j );
connections[j].push_back( i );
}
}
}
vector<bool> visited( N, false ); // the indices of divisors used thus far
vector<int> sequence; // contains the INDICES of the divisors
if ( DFS( 0, sequence, connections, visited ) )
{
for ( int e : sequence ) cout << divisors[e] << " ";
cout << '\n';
}
}
测试 1：
Enter N: 12
1 2 4 12 6 3
测试2：
Enter N: 100
1 2 4 20 10 5 25 50 100
测试 3：
Enter N: 123456789
1 3 9 32463 10821 3607 13717421 3803 11409 34227 123456789 41152263
3
-
“… 并且对于较大的 N 值来说，性能是一个问题” – 对于较大的值，主函数中的两个嵌套 for 循环会非常糟糕。如果将数字拆分为其素因数，则只需循环素因数的数量（和重复次数），而不是 n^2。当然，在最坏的情况下，N 本身可能是一个很大的素数，那么您仍然需要搜索大量不匹配的素数。
– -
我刚刚注意到，isPrime() 可以稍微优化一下，跳过前面调用中已经测试过的较低数字，无需再次测试相同的值。
– -
谢谢，@Thibe。主程序中的嵌套循环按 (除数数量)^2 而不是 n^2 缩放，因此它实际上取决于数字有多少个因数。不过，由于我已经对除数进行了排序，因此我可以将总循环数减少 2 倍。
–
|
–
–
int）或库名称（如）。 和 不等同于 吗？哦，和不会优化代码，只是可能使用（这不是瓶颈）。你在哪里学到这些狗屁东西的？你在上尝试过正确的 C++吗？endl1e3 + 71007optimizecin–
–
#define int那里就是未定义的行为。我甚至没有读到那部分。我撒谎了 – 我刚刚看到了std::int32_t main()。太糟糕了！–
|