回溯额 void backtrack(int n, int index, vector<bool>& visited, int & count) { if (index == n) { if (visited[n]) { count++; if (count == 1000000007) count = 0; return; } else { count++; if (count == 1000000007) count = 0; count++; if (count == 1000000007) count = 0; return; } } if (visited[index]) { backtrack(n, index + 1, visited, count); } else { for (int i = 0; i < 2; ++i) { if (0 == i) { int temp1 = index ; while (temp1 <= n) { visited[temp1] = true; temp1 += index; } backtrack(n, index + 1, visited, count); int temp2 = index ; while (temp2 <= n) { visited[temp2] = false; temp2 += index; } } else { visited[index] = true; backtrack(n, index + 1, visited, count); visited[index] = false; } } } return; } int main() { int n = 0; while(cin >> n) { vector<bool> visited(n+1, false); int count = 0; backtrack(n, 2, visited, count); cout << count << endl; } }