I am interested in the problem of finding a better master number identifier for years. I realize that this is a large area of academic research and study - my interest in this is to have fun here, my first attempt at a possible solution was here, in C (below)
My question is, Can you suggest improvements (referring to some other references on the net, I am searching for the actual C code)? What I am trying to achieve from this, there is a better understanding of the complexity of the functionality of such solutions.
Do I have the complexity of this closing o (n ^ 2)? / P>
#include & lt; Stdio.h & gt; # Include & lt; Math.h> / * Isprime * / / * Test if each number in the list is stdin * / / * Output will only print the main number in the list. * / Int main (int argc, char * argv []) {int returnValue = 0; Int i; Int. Ceiling; Int input = 0; Int factorFound = 0; While (scanf ("% d", and input)! = EOF) {roof = (int) sqrt (input); If (input == 1) {factorFound = 1; } For (i = 2; i & lt; = roof; i ++) {if (input% i == 0) {factorFound = 1; }} If (factorFound == 0) {printf ("% d \ n", input); } Factor = 0; } Return return value; } >
for (i = 2; i & lt; = roof ; I ++) {if (input% i == 0) {factorFound = 1; break; }} This is the first improvement to remain within the "first" algorithm, and still there is no math required to see it.
After this, once you see that the input is not divisible by 2, there is no need to check 4, 6, 8, etc. If any number is divided into input , of course 2, all this will also divide the numbers.
If you algorithms a bit, you can use that loop which provides it in its answer. (This comment is easy compared to correcting my code, though their efforts are greatly appreciated)
Takes advantage of the fact that besides 2 and 3, each principal form, To see it for some positive integer or n * 6 + 1 n * 6 - 1 , just note that if m = N * 6 + 2 or m = n * 6 + 4 , then divided by n 2. If the m = n * 6 + 3 then it is divisible by 3.
In fact, we can take it forward. If there are primes of p1, p2, .., pk before k , then all the integers that are on top of their product mark are 'slots' that should have all the remaining primarys < / P>
To view it, just give the product of all primeing up to K # to pk . So if divides the gcd (k #, m) = g , g n * k # + m and therefore this amount is equally comparable Composite is G! = 1 . So if you want to intersect in the context of 5 # = 30 , then your copreum integers are 1, 7, 11, 13, 17, 19, 23 and 29.
Technically, I did not prove my last claim. It is not too difficult
if g = gcd (k #, m) , then for any integer, n , g divided by n * k # + m because it splits k # , hence it is also divided into n * k # should do. But it splits the m and it can also divide the sum. After this I have proved it only for n = 1 . My bad
In addition, I should keep in mind that none of these algorithms has changed the basic complexity, it will still be O (N ^ 1/2). This is doing all the significantly reduces the coefficient which is used to calculate the actual expected time
Comments
Post a Comment