5. kotori和素因子（A组，B组）

题目：

代码：

include

using namespace std;
/
思路总结：
1.保存1000以内的质数—埃拉托斯特尼筛法
2.求出所有整数的所有素因子—动态二维数组
3.dfs求出最小素因子之和 /
int ans = 9999999;
int n;
int vis[10001];

vectorv[100];
const int MAX = 1001;
bool prime[MAX];
// 埃拉托斯特尼筛法
void init(){
fill(prime,prime + MAX,true); //初始化全为质数
for(int i = 2 ; i i < MAX; ++i){
if(prime[i]){
for(int j = i i; j < MAX; j+=i){
prime[j] = false;
}
}
}
}
void dfs(int d,int sum){//重点
if(d == n){//先写退出条件—深度达到最大值
ans = min(ans,sum);
return;
}
for(int i = 0; i < v[d].size(); i++){//从最底层开始，一次选一个值
if(!vis[v[d][i]]){
vis[v[d][i]] = 1;//标记该值，表已经被用过
dfs(d + 1, sum + v[d][i]); //选完一个换下一个
vis[v[d][i]] = 0; //上一个选完后回头，换一个路，将之前标记过的值还原
}
}
}
int main(){
init();
scanf(“%d”,&n);
for(int i = 0; i < n; i++){
int temp;
scanf(“%d”,&temp);
for(int j = 2; j <= temp; j++){
if(prime[j]&&temp % j == 0){
v[i].push_back(j);
}
}
}
dfs(0,0);
if(ans == 9999999) printf(“-1\n”);
else printf(“%d\n”,ans);
return 0;
}

c语言版

include

include

int ans = 9999999;
int n;
int vis[10001];

int v[100][100];
const int MAX = 1001;
int prime[MAX];

void init() {
memset(prime, 1, sizeof(prime)); // 初始化全为质数
for (int i = 2; i i < MAX; ++i) {
if (prime[i]) {
for (int j = i i; j < MAX; j += i) {
prime[j] = 0;
}
}
}
}

void dfs(int d, int sum) {
if (d == n) {
ans = ans < sum ? ans : sum;
return;
}
for (int i = 0; i < 100; i++) {
if (v[d][i] != 0 && !vis[v[d][i]]) {
vis[v[d][i]] = 1;
dfs(d + 1, sum + v[d][i]);
vis[v[d][i]] = 0;
}
}
}

int main() {
init();
scanf(“%d”, &n);
for (int i = 0; i < n; i++) {
int temp;
scanf(“%d”, &temp);
int k = 0;
for (int j = 2; j <= temp; j++) {
if (prime[j] && temp % j == 0) {
v[i][k] = j;
k++;
}
}
}
dfs(0, 0);
if (ans == 9999999) printf(“-1\n”);
else printf(“%d\n”, ans);
return 0;
}
错误点：
c语言没有vector 但不一定非要知道数组的大小，设置一个足够大的数组范围，判断其元素值不为0即可停止 (因为数组有效元素不为0)