{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"给出n个数,找出一个最大素数独立子集,如果a\u003db*一个素数,那么认为a是b的一个素数乘级,如果一个集合不存在一个数是另一个数的素数乘级,那么这就是素数独立子集。"}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 20)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e \n \u003cp class\u003d\"MsoNormal\"\u003eEach case starts with an integer \u003cb\u003eN (1 ≤ N ≤ 40000)\u003c/b\u003e denoting the size of the set. Next line contains \u003cb\u003eN\u003c/b\u003e integers separated by a single space. Each of these \u003cb\u003eN\u003c/b\u003e integers are distinct and between \u003cb\u003e1\u003c/b\u003e and \u003cb\u003e500000\u003c/b\u003e inclusive.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoNormal\"\u003eFor each case, print the case number and the size of the largest prime independent subset.\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e5\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 4 8 16 32\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e5\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e2 3 4 6 9\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003e1 2 3\u003c/span\u003e\u003c/p\u003e "}},{"title":"Sample Output","value":{"format":"HTML","content":" \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 1: 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 2: 3\u003c/span\u003e\u003c/p\u003e \u003cp class\u003d\"MsoNoSpacing\"\u003e\u003cspan style\u003d\"font-family:\u0026quot;Courier New\u0026quot;\"\u003eCase 3: 2\u003c/span\u003e\u003c/p\u003e "}},{"title":"Hint","value":{"format":"HTML","content":" \n \u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eAn integer is said to be a prime if it\u0027s divisible by exactly two distinct integers. First few prime numbers are \u003cb\u003e2, 3, 5, 7, 11, 13, ...\u003c/b\u003e\u003c/span\u003e\u003c/p\u003e \n \u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2.\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eDataset is huge, use faster I/O methods.\u003c/span\u003e\u003c/p\u003e \n \u003c/div\u003e \n \u003chr style\u003d\"color: #717171; height: .5px;\"\u003e \n \u003cdiv id\u003d\"problem_setter\"\u003e\n Problem Setter: Abdullah Al Mahmud \n \u003c/div\u003e \n \u003cdiv id\u003d\"problem_setter\"\u003e\n Special Thanks: Jane Alam Jan \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003cspan id\u003d\"showNavigation\" style\u003d\"display: none;\"\u003e \n \u003cdiv id\u003d\"navigation\"\u003e \n \u003cdiv class\u003d\"navcontainer\"\u003e \n \u003cul class\u003d\"navlist\"\u003e \n \u003cli class\u003d\"menutitle\"\u003eVolume\u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_index.php\"\u003e Volume Home \u003c/a\u003e \u003c/li\u003e \n \u003cli id\u003d\"active\"\u003e \u003ca id\u003d\"current\" href\u003d\"http://lightoj.com/volume_problemset.php\"\u003e Problem Set \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_problemset.php?volume\u003d10\"\u003e Volume 10 \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_problemset.php?volume\u003d11\"\u003e Volume 11 \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_problemset.php?volume\u003d12\"\u003e Volume 12 \u003c/a\u003e \u003c/li\u003e \n \u003cli id\u003d\"active\"\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_problemset.php?volume\u003d13\"\u003e Volume 13 \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_problemset.php?volume\u003d14\"\u003e Volume 14 \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_problemcategory.php\"\u003e Problem Category \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_problemsetters.php\"\u003e Problem Setters \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_submit.php\"\u003e Submit Problem \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_usersubmissions.php\"\u003e My Submissions \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_submissions.php\"\u003e Judge Status \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"\"\u003e Ranklist \u003c/a\u003e \u003c/li\u003e \n \u003cspan id\u003d\"subactive\" style\u003d\"display: none;\"\u003e \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_ranklist.php\"\u003e Full Ranklist \u003c/a\u003e \u003c/li\u003e \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_country_ranklist.php\"\u003e Country Ranklist \u003c/a\u003e \u003c/li\u003e \n \u003c!--\n\t\t\t\t\u003cli \u003e\n\t\t\t\t\t\u003ca class\u003d\"submenu\" href\u003d\"asd\"\u003e\n\t\t\t\t\t\tUniversity Ranklist\n\t\t\t\t\t\u003c/a\u003e\n\t\t\t\t\u003c/li\u003e\n\t\t\t\t!--\u003e \u003cli\u003e \u003ca class\u003d\"submenu\" href\u003d\"http://lightoj.com/volume_ranklist.php?type\u003dfriend\"\u003e Friends Ranklist \u003c/a\u003e \u003c/li\u003e \u003c/span\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_userstat.php\"\u003e User Statistics \u003c/a\u003e \u003c/li\u003e \n \u003cli\u003e \u003ca href\u003d\"http://lightoj.com/volume_compare_userstat.php\"\u003e Compare User Statistics \u003c/a\u003e \u003c/li\u003e \n \u003cli class\u003d\"menubottom\"\u003e\u0026nbsp;\u003c/li\u003e \n \u003c/ul\u003e \n \u003c/div\u003e \n \u003c/div\u003e \u003cscript src\u003d\"\"\u003e\n\tfunction handleSubMenu( ) {\n\t\tif( document.getElementById(\"subactive\").style.display \u003d\u003d \"none\" ) {\n\t\t\tdocument.getElementById(\"subactive\").style.display \u003d \"inline\";\n\t\t}\n\t\telse {\n\t\t\tdocument.getElementById(\"subactive\").style.display \u003d \"none\";\n\t\t}\n\t}\n\u003c/script\u003e \u003c/span\u003e \n \u003cdiv class\u003d\"bottomDiv\" align\u003d\"center\"\u003e \n \u003ctable width\u003d\"100%\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"50%\"\u003e \n \u003cdiv class\u003d\"midMessage\"\u003e\n Developed and Maintained by \n \u003cbr\u003e\n \u003cb\u003eJANE ALAM JAN\u003c/b\u003e \n \u003c/div\u003e \u003c/td\u003e \n \u003ctd width\u003d\"50%\"\u003e \n \u003cdiv class\u003d\"midMessage\"\u003e\n Copyright © 2012 \n \u003cbr\u003e\n \u003cb\u003eLightOJ, Jane Alam Jan\u003c/b\u003e \n \u003c/div\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e \n "}},{"title":"","value":{"format":"HTML","content":""}}]}