how to solve ALICESIE on spoj. How it has common pattern for its answer


how to solve ALICESIE on spoj. How it has common pattern for its answer



What is the logic behind pattern i.e.(ans=(n+1)/2) in question ALICESIE on spoj.

Algorithm_given:
1.Create a list of consecutive integers from N to 2 (N, N-1, N-2, ..., 3, 2). All of those N-1numbers are initially unmarked.
2.Initially, let P equal N, and leave this number unmarked.
3.Mark all the proper divisors of P (i.e. P remains unmarked).
4.Find the largest unmarked number from 2 to P – 1, and now let P equal this number.
5.If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

Find total number of unmarked numbers.




i know its O(sqrt(n)) solution but answer is expected in O(1),it can found by seeing the common pattern i.e.(N+1)/2
But how to prove it Mathematically

link: ALICESIE





I'm voting to close this question as off-topic because it is a "link-only" question; its meaning depends on a document elsewhere, which could change or vanish at any time.
– Beta
Jul 1 at 0:14





so should i paste whole question here
– Navneet Hingankar
Jul 1 at 0:29





Yes, you should paste or summarize the question here. Just as important, you should show us some of the work you have done on the problem. We will not do all the work in helping you in a contest.
– Rory Daulton
Jul 1 at 0:39





You did a pretty good job in summarizing the problem, so your question is no longer link-only. The question is now improved. However, you still have not shown any work of your own on the problem. Also, the question now is clearly a mathematics problem, even if it was stimulated by a programming problem. You should ask this question at Mathematics Stack Exchange after adding more of your own work and explaining just where you are stuck.
– Rory Daulton
Jul 1 at 5:42





actually i dont know how to prove it,as for me its just coincidence, but there must be mathematical proof behind it, i want to just perceive that.
– Navneet Hingankar
Jul 1 at 7:01









By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

-

Popular posts from this blog

How to input without newline? (Python)

How to input without newline? (Python) I am trying to create a simple file editor in Python via the console (called PyCons). Here is my current program: def PyCons(f): file = open(f, "r") appe = open(f, "a") print("n=====nPyCons Editor, v1.2nPython 3.6.1n") global i i = 0 for line in file: i += 1 print(" {}| ".format(i) + line, end='') for k in range(10000000000000): print("n {}| ".format(i+1), end='') inp = input("") if inp == "@PyCons.save()": print("n=====") break else: i += 1 appe.write("n" + inp) I used the end method to make sure that the existing code in the file was printed properly in its line format, but the input function does not have an end attribute. So, when I go to enter code in the editor: end input end PyCons("magic.html") ... ===== PyCons Editor, v1.2 Python 3.6.1 1| <p>Hello!...
Read more

C++ thread error: no type named ‘type’ MINGW

C++ thread error: no type named ‘type’ MINGW I'm currently doing a project for my operational systems class and I have to make a program to find prime numbers to run in threads. So I did this: #include <iostream> #include <cmath> #include <thread> #define THREADNUMBER 100 using namespace std; int CONTADOR = 0; int CONTADORTHREADEXECUTADA = 0; int primeRange(int v1, int v2) { int a, limit; bool isprime; for (int i = v1; i <= v2; i++) { if (i % 2 != 0 && i % 3 != 0) { isprime = true; limit = i / 2; if(i == 1) isprime =false; limit = (int)sqrt(i); //General case for(a=2; a <= limit; a++){ if(i % i == 0 && i != 2){ isprime = false; break; } } if (isprime) { CONTADOR++; } } } CONTADORTHREADEXECUTADA++; return 1; } int main(int argc, char *argv[ ] ) { int number1 = atoi(argv[1]); int num...
Read more

Analog for TagView in flutter

Image
Analog for TagView in flutter I want to have UI like this: With native Android it can be done with libraries like https://github.com/whilu/AndroidTagView, how can it be done with flutter? 2 Answers 2 you can make the same UI by combining the Wrap and Chip widget as @wasyl montioned . but this is a full example about what you need Wrap Chip Notes : spacing deleteIcon avatar Chip Shape new Column( crossAxisAlignment: CrossAxisAlignment.stretch, children: <Widget>[ new Wrap( children: <Widget>[ Chip( label: new Text("Java"), onDeleted: () {}, labelPadding: EdgeInsets.all(2.0), deleteIcon: Icon(Icons.clear), ), Chip( label: new Text("C++"), onDeleted: () {}, labelPadding: EdgeInse...
Read more