【C# 每日一题8】一道纠结的问题
DescriptionGiven an infinite array of integers 2,3,.... Now do some operations on it.The operation is to choose a minimum number from the array which is never been chosen, then change the status of its multiples excluding itself, i.e remove the multiples of the chosen number if they are in the array , otherwise add it to the array.keep the order after change.For instance, the first step, choose number 2, change the status of 4, 6, 8, 10... They are all removed from the array. The second step, choose 3, change the status of 6, 9, 12, 15...Pay attention: 9 and 15 are removed from the array while 6 and 12 are added to the array.InputEvery line contains an integer n. The zero value for n indicates the end of input.OutputPrint "yes" or "no" according whether n is in the array.Sample Input230900Sample OutputyesyesnoHintThe number n never has a prime factor greater than 13000000, but n may be extremely large.
int num = int.Parse(Console.ReadLine()); bool[] a = new bool[num + 2]; for (int i = 0; i < num + 2; i++) { a[i] = true; } for (int i = 2; i < num + 2; i++) { if (a[i] == true) { for (int j = i + 1; j < num + 2; j++) { if (j % i == 0) { if (a[j] == false) a[j] = true; else a[j] = false; } } } } int n = int.Parse(Console.ReadLine()); Console.WriteLine("The result is " + a[n]);
[解决办法]
List<uint> list = new List<uint>(); uint temp; string str; while (true) { Console.WriteLine("请输入一个状态数字<Q=Exit>:"); try { str = Console.ReadLine(); if (str == "Q" || str == "q") { break; } temp = uint.Parse(str); if (temp > 1) { list.Add(temp); } else { Console.WriteLine("必须为大于等于2的数字"); } } catch { Console.WriteLine("输入错误!请输入一个正整数"); } } bool state = false; while (true) { Console.WriteLine("请输入一个要查询的数字<Q=Exit>:"); try { str = Console.ReadLine(); if (str == "Q" || str == "q") { break; } temp = uint.Parse(str); if (temp > 1) { foreach (uint u in list) { if (temp % u == 0) { state = true; break; } else { state = false; } } if (state) { Console.WriteLine("已改变"); } else { Console.WriteLine("未改变"); } } else { Console.WriteLine("必须为大于等于2的数字"); } } catch { Console.WriteLine("输入错误!请输入一个正整数"); } }
[解决办法]
枚举n所有公约数，存于数组，先剔除所有质数的乘方数（只能被改变一次），统计能存在的公约数个数，为奇则此数不存在，为偶则存在，（判断公约数是否存在：质公约数必然存在，和数公约数则对其重复此过程）
[解决办法]
修改了下，效率好很多了~
int num = int.Parse(Console.ReadLine()); bool[] a = new bool[num]; for (int i = 0; i < num; i++) { a[i] = true; } for (int i = 2; i < num; i++) { if (a[i] == true) { int j = 2 * i; while (j < num) { a[j] = !a[j]; j += i; } } } int n = int.Parse(Console.ReadLine()); Console.WriteLine("The result is " + a[n]);
[解决办法]
Console.WriteLine("Please input total numbers!"); long num = long.Parse(Console.ReadLine()); Console.WriteLine("Please input the number you want to find!"); long n = long.Parse(Console.ReadLine()); if (num < n) { Console.WriteLine("No!"); return; } long i = 2; while (i * i <= n) { if (n % (i * i) == 0) { Console.WriteLine("No!"); return; } i++; } Console.WriteLine("Yes!");
------解决方案--------------------
class Solver{ static List<int> Primes = new List<int>(); static Solver() { bool[] masks = new bool[13000000]; for(int i=0; i<masks.Length; i++) masks[i] = true; for (int i = 2; i < masks.Length; i++) { if (masks[i]) { Primes.Add(i); for (int j = i + i; j < masks.Length; j += i) { masks[j] = false; } } } } public static bool OnOffState(long i) //<--- { foreach (int prime in Primes) { if (i % prime == 0) { i /= prime; if (i % prime == 0) return false; } if (i < prime * prime) break; } return true; }}
[解决办法]