Certifying entanglement of a multipartite state is generally considered a demanding task. Since an N qubit state is parametrized by 4^{N}-1 real numbers, one might naively expect that the measurement effort of generic entanglement detection also scales exponentially with N. Here, we introduce a general scheme to construct efficient witnesses requiring a constant number of measurements independent of the number of qubits for states like, e.g., Greenberger-Horne-Zeilinger states, cluster states, and Dicke states. For four qubits, we apply this novel method to experimental realizations of the aforementioned states and prove genuine four-partite entanglement with two measurement settings only.